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 this 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).Write a program to implement the above algorithms for solving the Selection Problem and compare the times. Select-kth 1 is to implement Algorithm 1 using the O(nog n) Mergesort sorting method. Select-kth 2 will implement the Algorithm 2 using the partition procedure of Quicksort iteratively and Select-kth 3 will implement the Algorithm 2 recursively. Select-kth 4 is a recursive procedure to implement the Algorithm 3 with mm rule. Run your program for n = 10, 50, 100, 250, 500, 1000, ... (with k = 1, n/4, n/2, 3n/4, and n). In order to obtain more accurate results, the algorithms should be tested with the same list of numbers of different sizes many times. The total time spent is then divided by the number of times the selection is performed to obtain the time taken to solve the given instance. Remember to verify the correctness of your implementation of the four algorithms.

Question

16-12-2022
Computers and Technology

contestada

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 this 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).Write a program to implement the above algorithms for solving the Selection Problem and compare the times. Select-kth 1 is to implement Algorithm 1 using the O(nog n) Mergesort sorting method. Select-kth 2 will implement the Algorithm 2 using the partition procedure of Quicksort iteratively and Select-kth 3 will implement the Algorithm 2 recursively. Select-kth 4 is a recursive procedure to implement the Algorithm 3 with mm rule. Run your program for n = 10, 50, 100, 250, 500, 1000, ... (with k = 1, n/4, n/2, 3n/4, and n). In order to obtain more accurate results, the algorithms should be tested with the same list of numbers of different sizes many times. The total time spent is then divided by the number of times the selection is performed to obtain the time taken to solve the given instance. Remember to verify the correctness of your implementation of the four algorithms.

Respuesta :

Otras preguntas

PLEASE PLEASE HELP 1. Using a neutral atom that has an atomic number of 28 and a mass number of 152, how many protons, electrons and neutrons are in this atom?

The movement from C1 to C2 on the production possibilities curve above could be caused by A) a loss of resources used in the production of consumer goods. B) n

Sara decides to host a party for her new American friends. She tells them that the party will begin at 8pm. She is shocked when most of her guests arrive at or

What is 3 to the 6 power over 3 to the 10 power times 3 to the 1 power equal

Victor owns a highly successful bakery and coffee shop, Mocha & Muffins. Others have expressed interest in starting nearly identical shops at various locati

What are three situations you would stop care for a conscious choking adult or infant

For a particular experiment, Maria must heat water in a glass flask using a Bunsen burner. She then needs to move the flask from the burner to the lab bench. Wh

A large pond is stocked with fish. The fish population P is modeled by the formula P = 2t + 8 t + 110, where t is the number of days since the fish were first i

What is the correct formula for density?

A sample of 9.3 grams of NaOH is dissolved into 555 mL of aqueous 0.250 M NaOH (assume no volume change). This solution is then poured into 2.25 gallons of wate

ACCESS MORE

aashvi1 aashvi1 · Answer 1 · 2022-12-21T08:30:13+01:00

First, let's use the method in its simplest implementation. So, given an unsorted array of various values and asked to print the kth smallest element, the easiest way is to sort it and then to the k-1th position To return an element (considering 0-based indexing) .

To do this, first sort the array, then access the k-1th index containing the kth smallest element of the array.

The time complexity of this method is O(N* log N) due to the sorting algorithm used.

The space complexity of the method depends on the sorting algorithm used. For example, O(N) when using merge sort and O(1) when using heapsort.

Which approach can be used for identifying the kth smallest?

There is a much better approach to finding Kth smallest element, which relies on median-of-medians algorithm. Basically any partition algorithm would be good enough on average, but median-of-medians comes with the proof of worst-case O(N) time for finding the median.

How do you choose the K smallest number from N numbers?

The basic idea here is to create a minimal heap of all n elements and extract the minimal element K times. The last element extracted is the Kth smallest element. Extract the smallest element K-1 times. H. Delete the root and perform K heap operations.

To know more about unsorted array visit;

https://brainly.com/question/16910794

#SPJ4