Two clarifications for lecture 4

1. Some student pointed out after class that there is a typo in my analysis of the randomized selection algorithm. We should have d = 4c instead of d = 4cn.

Also, the pivot point we get for the deterministic selection algorithm should have the property that 0.3n <= i <= 0.7n where a_i is the pivot point. I may write 0.3n < a_i < 0.7n instead.


2. One student asked in the class what if there are many numbers of the same value in the selection problem.  Another student immediately told me after class that the following quick fix: create a list called E for all the numbers that are equal to the pivot number a_i..

We will then have three lists L, E, G.  Since we know the length of L, E, G, we can still figure out whether the k-th smallest number is in L, E, or G. If it is in E, we can simply output a_i; if it is in L, we will apply Select(L,k); if it is in G, we will apply Select(G, k-|L|-|E|).