From Mohammed J. Zaki

IntroAlgorithms: Lab4

Lab 4: Selection Due Wed 14th Feb, During Lab

Implement the randomized (divide and conquer) selection algorithm described in section 2.4 in the book that returns the k-th smallest value in an array of n integers.

Your code should input \(n\) and \(k\) as command line parameters. Next generate an array of \(n\) random integers in the range [\( 0,n-1 \)]. You should generate these \(n\) integers independently so that you can have duplicate values in the array.

Your code should return the k-th smallest value in the array. Note that k ranges from 1 to n, i.e., k=1 means return the smallest value, k=10 means returns the 10-th smallest value, and so on.


Print out the k-th smallest value in the array, followed by the original array, and the sorted array. For example, on the array [5, 8, 9, 5, 0, 0, 1, 7, 6, 9] the output for k=3 should be:
select 1
array [5, 8, 9, 5, 0, 0, 1, 7, 6, 9]
sorted array [0, 0, 1, 5, 5, 6, 7, 8, 9, 9]
That is, the 3rd smallest value is 1, as we can see from the sorted array.

Test you code on larger n and k values. Note that for sorting you can use the inbuilt Python sort function. It is just for testing your output.

You will find the Python numpy module very useful for this assignment. For example, you can use numpy.random.randint to generate random integers.

Retrieved from http://www.cs.rpi.edu/~zaki/www-new/pmwiki.php/IntroAlgorithms/Lab4
Page last modified on February 13, 2018, at 08:59 AM