Given a list of n numbers, the Selection Problem is to find the kth smallest element...

 

Transcribed Image Text:

Given a list of n numbers, the Selection Problem is to find the kth smallest element in the list. The first algorithm (Algorithm 1) is the most straightforward one, i.e. to sort the list and then return the kth smallest element. It takes O(n log n) amount time. The second algorithm (Algorithm 2) is to apply the procedure Partition used in Quicksort. The procedure partitions an array so that all elements smaller than some pivot item come before it in the array and all elements larger than that pivot item come after it. The slot at which the pivot item is located is called the pivotposition. We can solve the Selection Problem by partitioning until the pivot item is at the kth slot. We do it by recursively partitioning the left subarray if k is less than pivotposition, and by recursively partitioning the right subarray if k is greater than pivotposition. When k = pivotposition, we're done. The best case complexity of this algorithm is O(n) while the worst case is O(n2). The third algorithm (Algorithm 3) is to apply the Partition algorithm with the mm rule and it's theoretical worst case complexity is O(n). Program the following three algorithms that we covered in the class: Algorithm 1: find the kth smallest element in the list using the O (n log n) Mergesort sorting method. Algorithm 2: find the kth smallest element in the list using partition procedure of Quicksort recursively. Algorithm 3: find the kth smallest element in the list using partition procedure of Quicksort recursively via Medians of Medians (mm). You can use either Java, or C++ for the implementation. The objective of this project is to help student understand how above three algorithms operates and their difference in run-time complexity (average- case scenario). The project will be divided into three phases to help you to accomplish above tasks. They are Part 1: Design and Theoretical analysis, Part 2: Implementation, and Part 3: Comparative Analysis. Given a list of n numbers, the Selection Problem is to find the kth smallest element in the list. The first algorithm (Algorithm 1) is the most straightforward one, i.e. to sort the list and then return the kth smallest element. It takes O(n log n) amount time. The second algorithm (Algorithm 2) is to apply the procedure Partition used in Quicksort. The procedure partitions an array so that all elements smaller than some pivot item come before it in the array and all elements larger than that pivot item come after it. The slot at which the pivot item is located is called the pivotposition. We can solve the Selection Problem by partitioning until the pivot item is at the kth slot. We do it by recursively partitioning the left subarray if k is less than pivotposition, and by recursively partitioning the right subarray if k is greater than pivotposition. When k = pivotposition, we're done. The best case complexity of this algorithm is O(n) while the worst case is O(n2). The third algorithm (Algorithm 3) is to apply the Partition algorithm with the mm rule and it's theoretical worst case complexity is O(n). Program the following three algorithms that we covered in the class: Algorithm 1: find the kth smallest element in the list using the O (n log n) Mergesort sorting method. Algorithm 2: find the kth smallest element in the list using partition procedure of Quicksort recursively. Algorithm 3: find the kth smallest element in the list using partition procedure of Quicksort recursively via Medians of Medians (mm). You can use either Java, or C++ for the implementation. The objective of this project is to help student understand how above three algorithms operates and their difference in run-time complexity (average- case scenario). The project will be divided into three phases to help you to accomplish above tasks. They are Part 1: Design and Theoretical analysis, Part 2: Implementation, and Part 3: Comparative Analysis.