Given an array A[ ] of n elements and an integer k in the range [1, n], the functionSELECT (dtype A[ ], int n, int k)returns the kth smallest element of the array. (For example, k = 1 is the smallest element, k = n is thelargest, and k = n/2 is the median.) In this programming assignment, you are to implement SELECTusing three different algorithms as described below, and compare their performance in terms of the numberof key comparisons. (Do not perform the key comparisons in-line. Rather, use a function to perform eachkey comparison, while incrementing a counter.)

1. SELECT1: Sort the array using Quicksort and pick the kth smallest element. This has average timecomplexity of O(n log n) and worst-case time of O(n2).

 

 

CS 610Programming Assignment2Prof. D. NassimiAlgorithmsDue: Week 10, Wed. Nov. 9Fall 2016Given an arrayA[ ] ofnelements and an integerkin the range [1,n], the functionSELECT (dtypeA[ ], intn, intk)returns thekth smallest element of the array. (For example,k= 1 is the smallest element,k=nis thelargest, andk=n/2 is the median.) In this programming assignment, you are to implement SELECTusing three different algorithms as described below, and compare their performance in terms of the numberofkey comparisons. (Do not perform the key comparisons in-line. Rather, use a function to perform eachkey comparison, while incrementing a counter.)1. SELECT1: Sort the array using Quicksort and pick thekth smallest element. This has average timecomplexity ofO(nlogn) and worst-case time ofO(n2).2. SELECT2: Randomized selection. (The textbook calls it Quick-Select, p.246.) This algorithm hasan average time complexity ofO(n) and a worst-case time ofO(n2).(a) Ifn <25, sort the array using insertion sort, and return thekth element. Otherwise, continue.(b) Pick a pivot elementVin random and use it to partition the elements into three sets (L,E,G) ofelements less thanV, equal toV, and greater thanV, respectively. Let the number of elementsin these sets ben1,n2,n3. Use the sizes of these sets to determine where thekth smallest elementfalls, and make a recursive call accordingly. That is:Ifk≤n1then SELECT2 (L,n1,k);else ifk≤n1+n2then return (V);else SELECT2 (G,n3,k-n1-n2).3. SELECT3: Selection algorithm with linear worst-case time, but with a large constant factor. (Thisalgorithm is discussed in class and is also discussed in exercise C-4.24, p. 254, of the textbook.) Thealgorithm is outlined below.(a) Ifn <25, sort the array using insertion sort, and return thekth element. Otherwise, continue.(b) Divide the set ofnelements into subsets (“rows”) of size 5 each, and find the median of eachsubset. (Ifnis not a multiple of 5, the last row will have less than 5 elements.) To find themedian of each row of 5, you can simply use bubble-sort or insertion sort. To avoid the need fora second array, you can pack then/5 row-medians in front of the same array as they are found.(Use swap operations for this packing to preserve all elements.)(c) Make a recursive call to SELECT3 to find the median of then/5 row-medians.(d) Use this median-of-medians as the pivotVto partition the array ofnelements into three sets asbefore. Then make a recursive call to SELECT3 for either the left or right partition as needed.Run experiments for the following values ofn: 10 000, 100 000, and 1000 000. For each value ofn, producean array of randomly generated elements. (You may use integers.) Then use each of the three methods tofind thekth smallest element fork=n/2, and print one line result:Algorithm X:n,k,A[k], Number of Key-Comparisons.(Be sure the same original array ofnelements is used for all three methods.) Tabulate the performanceresults for the three algorithms. Explain how the results compare with the expected analytical results, andhow the three algorithms compare against each other.1

Attachments:

• 1494305871-cs610-p2-selection.pdf