Starting from:
$29.99
Assignment 1: Quickselect with the Median-of-Medians Pivot
Quickselect with the Median-of-Medians Pivot
1 Programming Assignment
The assignment is to design and implement Quickselect with the median-of-medians pivot, where the medians are of groups of size 7. Input: An array A of n integers and an integer k in the set {1,2,...,n}. Output: The k th smallest element of A. AJavatemplatehasbeenprovidedcontaininganemptyfunctionQuickSelect, which takes an integer array A and an integer k as arguments, and returns the k th smallest element of A. Your task is to write the body of the QuickSelect function. In case of incorrect inputs, you should return −1. You must use the provided Java template as the basis of your submission, and put your implementation inside the QuickSelect function in the template. You may not change the name, return type or parameters of the QuickSelect function or the class. Themainfunctioninthetemplatecontainscodetohelpyoutestyourimplementation by entering test data or reading it from a file. You may modify the main function, but only the contents of the QuickSelect function will be marked, since the main function will be deleted before marking begins.
2 Examples The table below shows the correct output of the QuickSelect function on various test inputs.
Input Array A k Output 10, 35, 12, 243 2 12 1, 24, 3, 70 1 1 85, 100, 99, 50 5 −1 85 1 85
3 Grading The programming assignment will be marked out of 40, based on a combination of automated testing (using large test arrays similar to the ones posted on conneX) and human inspection. There are several possible implementations for Quickselect. For an input array containing n values, the optimal implementation is O(n). The mark for each submission will be based on both the asymptotic worst case running time and the ability of the algorithm to handle inputs of different sizes. The table below shows the expectations associated with different scores. Score Description 0 - 15 Submission does not compile or does not conform to the provided template. 16 - 30 The implemented algorithm is not O(n) or is substantially inaccurate on the tested inputs. 31 - 40 The implemented algorithm is O(n) and gives the correct answer on all tested inputs.
1 Programming Assignment
The assignment is to design and implement Quickselect with the median-of-medians pivot, where the medians are of groups of size 7. Input: An array A of n integers and an integer k in the set {1,2,...,n}. Output: The k th smallest element of A. AJavatemplatehasbeenprovidedcontaininganemptyfunctionQuickSelect, which takes an integer array A and an integer k as arguments, and returns the k th smallest element of A. Your task is to write the body of the QuickSelect function. In case of incorrect inputs, you should return −1. You must use the provided Java template as the basis of your submission, and put your implementation inside the QuickSelect function in the template. You may not change the name, return type or parameters of the QuickSelect function or the class. Themainfunctioninthetemplatecontainscodetohelpyoutestyourimplementation by entering test data or reading it from a file. You may modify the main function, but only the contents of the QuickSelect function will be marked, since the main function will be deleted before marking begins.
2 Examples The table below shows the correct output of the QuickSelect function on various test inputs.
Input Array A k Output 10, 35, 12, 243 2 12 1, 24, 3, 70 1 1 85, 100, 99, 50 5 −1 85 1 85
3 Grading The programming assignment will be marked out of 40, based on a combination of automated testing (using large test arrays similar to the ones posted on conneX) and human inspection. There are several possible implementations for Quickselect. For an input array containing n values, the optimal implementation is O(n). The mark for each submission will be based on both the asymptotic worst case running time and the ability of the algorithm to handle inputs of different sizes. The table below shows the expectations associated with different scores. Score Description 0 - 15 Submission does not compile or does not conform to the provided template. 16 - 30 The implemented algorithm is not O(n) or is substantially inaccurate on the tested inputs. 31 - 40 The implemented algorithm is O(n) and gives the correct answer on all tested inputs.
1 file (136.3KB)
