Find kth smallest element of n numbers. Assume k <=(n/2)?

Consider the problem of finding the k-th smallest element of a set of n numbers.


Assume that k %26lt;= (n/2).


However, instead of being able to look at the whole date set at once, you are given the numbers one by one in random order. To be precise, the input is a randomly ordered sequence of n numbers x1, x2,..,xn, given one at a time, inserted into a fixed memory cell C. That is, on the i-th input step the contents of xi are placed into C (and the previous contents of C are erased). You can perform any computation between two input steps (including moving the contents of C to a temporary storage location).


a. Suppose that we are interested only in minimizing the amount of storage used by the algorithm.


1. Prove a lower bound that shows any algorithm that finds the k-th smallest number requires k storage cells in addition to C.


2. Give an algorithm that achieves the lower bound you just proved. What is the running time?


b. Now, suppose we want to have a fast running time but still use very little space (though not necessarily the absolute minimum amount of space). Design an O(n) expected time algorithm to find the k-th smallest element using only O(k) storage. You may assume that the value of k is known ahead of time but the value of n is not known until the last element is seen.

Find kth smallest element of n numbers. Assume k %26lt;=(n/2)?
Crazy.. that's a nice question. is that saying that the kth element will appear in the first half of the list of numbers??. if so then only read to the halfway point.





I'm not sure which bit you want answered. But the last part is the thing that interest me, although i'm not sure that i have understood the question well. anyway...


if I was to find the Kth smallest element. I would keep a sorted vector or K elements. as the elements come in they would be compared to the last element of the vector and tested to see if it was smaller. the the last element is removed, bubble sort the new element(no need for anything fancy, Note if you use quick sort the algorithm may explode to O(k^2)). Then after the input has finished read the last element in the vector and bingo there is you kth element.
Reply:A. If you don't assume that you know the value of k, then the problem cannot be solved in any space less than capturing the entire list of n numbers.


B. Are duplicates allowed? How are they considered in terms of defining 'k'? for instance, if you want the 10th element, and the first ordered 6 values are 1,2,2,3,3,3 do they count as 6 or as 3 elements?


C. The maximum efficient solution is to store all N values, bubble sort them (requires 1 additional memory location) and then cycle through the sorted list using temporary counters. Plus you need to store 'k' somewhere.


D. You don't need, necessarily 'k' storage cells, if all you need is the kth value. Unless, of course, 'k' is very small (%26lt; 6). Why? Here's the algorithm:





0. Store 'k' and the first value.


1. capture the next value.


2. increment the count of number of values by 1


3. compare the next value to the stored value.


4. compare the count to k.


5. IF count %26lt; k, then store the greater of stored value and current value into stored value.


6. IF count %26gt; k, then store the lesser of stored value and current value into stored value.


7. Repeat, beginning at step 1 until there are no more values.





Yes? No?

quince