Assignment 2- Algorithm 1: Randomized selection

CS303–Spring, 2019 Programming Assignment 2 
Homework will be due at the BEGINNING of class on the date due. Your answers should be written
legibly if handwritten and your name should be clearly written on your homework assignment. Try to make
your answers as clear and concise as possible; style will count in your overall mark. Be sure to read and
know the collaboration policy in the course syllabus.
Assignments are expected to be turned following these requirements:
• Submit via blackboard with a zip file, both the write-up and code should be included. Use
your name as the zip file name. Try to make sure your code can compile and run, you
will lose most of the scores if your code can not run. If there are bugs that you can’t
fix, try to address them in your write-up. If you prefer to do late submission and take
the penalty, please inform TA and professor before the deadline.
• Try to answer the question 2 the question 3 with details and show your test cases(output screenshot)
for these algorithms in the write-up.
Problems In this assignment you are asked to implement three different algorithms for median finding,
or more generally for selection of the k’th smallest element in an unordered array. You will then be asked
to compare these algorithms. The three algorithms have the same input and output:
Input: an unordered array A[1, ..., n] and a number k such that 1 <= k <= n
Output: the k-th smallest element in A.
For example, the output of A = [9, 14, 9, 5, 10, 6, 15, 6, 13, 9] and k = 5 should be 9. Please test your
code and cover corner cases.
1. Algorithm 1: Randomized selection(10pts)
This is the algorithm we cover in class. Notes in Chapter 13.5(page 728 -729) of the textbook.
2. Algorithm 2: Deterministic selection (median of medians, 20pts)
Given a Although the randomized selection algorithm runs in time O(n) in expectation, it is actually
possible to design a deterministic algorithm for selection which also runs in time O(n). The main
difference between the deterministic selection algorithm and the randomized selection algorithm in
Section 13.5 of the textbook is how to choose the pivot. In Algorithm 2, divide A into groups of
5 elements (except the last group), then compute the medians M[1, .., n/5] of these groups using
sorting (which takes O(1) per group), then use the selection algorithm recursively to compute the
median of M[1, .., n/5] and use this value as the pivot to divide A into Sl, Sv, and Sr as before.
When the size of input A is not too large (e.g., no more than 10) you are allowed to use any sorting
algorithm (quicksort, mergesort, bubblesort, etc.). If you need more details, feel free to look at the
following Lecture Notes in https://www.ics.uci.edu/~eppstein/161/960130.html.
3. Algorithm 3: Sorting(20pts)
Implement Quicksort (page 731-732 of textbook), then use it to sort A, and return the k
0
th smallest
element. Note that most of the code for Quicksort should be very similar to your Algorithm 1.
Quicksort runs in expected O(nlogn) time.
1
• Show outputs(your code screenshots) for [7, 2, 4, 6, 9, 11, 2, 6, 10, 6, 15, 6, 14, 2, 7, 5, 13, 9,
12, 15], k = 10.
• Generate a random list of n = 107
integers, with each random integer being uniformly distributed
between 0 and n/100. Use your three algorithms to compute the median of this list (the n/2
smallest element), and time the running time of each algorithm. Depending on your machine
and implementation, this may take a few minutes; we suggest starting with smaller n first to
make sure everything is working properly.
Which algorithm performs the best? What if you make the list size n even larger?
2