![[topimage]](IMADA_en.png)
Exercises
- CLRS Exercise 7.4-5. The formulation is "argue", so no formal proof required, but argue for both parts in the big-O.
- CLRS Problem 7-1 a-b.
- CLRS Problem 7.2.
- CLRS Problem 7.4. Don't worry about rounding up or down when considering a complexity analysis.
- CLRS Exercises 9.2-1.
- CLRS Problem 9.1. At this point in the course, you have only seen a randomized algorithm for selection, but for this problem, just assume that one can run selection in worst-case \( O(n) \).
-
Assume that for an oral exam, there are \( k \) questions that students can draw from.
KimThe hypothetical lecturer finds it tiring to hear the same topic several times, so when a student draws a question, he doesn't put it back again for the next student. Thus, when the first student in the exam sequence draws, there are \( k \) questions laid out on the table, when the second student draws, there are only \( k-1 \) questions on the table, etc. The \( i \)th student sees a table with \( k-i+1 \) questions. At some point, the lecturer restarts the process with all \( k \) questions.The students employ different algorithms for selecting; some try to choose uniformly at random, some take the nearest, some the one furthest away, etc. The lecturer, on the other hand, places the questions in an order chosen uniformly at random, and either does not change the order in between questions disappearing, or sometimes collects all the questions currently on the table and places them uniformly at random again.
Are the students treated fairly in the sense that the \( i \)th student gets any of the question with probability \( 1/k \), i.e., independent of the person's placement in the exam sequence?