Question

program in python

Randomness can be used to improve the performance of deterministic algorithms which need to make many choices. Rather than repeatedly making fixed, hard-coded choices, a pseudorandom number generator can be used to make dynamic, unbiased choices. If the benefits of "good" choices outweigh the costs of "bad" choices, a random selection of good and bad choices can improve the performance of an algorithm Let us explore this with the QUICKSELECT algorithm. Discovered by the influential computer science pioneer Sir Tony Hoare in 1960 at the same time as the closely related sorting algorithm QUICKSORT, QUICKSELECT is an important and widely used algorithm for selecting the kth largest element of a list QUICKSELECT is a divide-and-conquer algorithm, which achieves its efficiency by re- peatedly splitting the list into parts. It does so by choosing a pivot element, and splitting the list into three parts--those elements less than the pivot, those equal to the pivot, and those greater than the pivot. By comparing the lengths of these three parts, it can deter- mine which of the three parts the kth largest element belongs to. It can then discard the other two parts and repeat the procedure with the one remaining part. (If that part is the middle, pivot part, then the algorithm can simply return the pivot.) The efficiency of QUICKSKLRCT depends on the choice of pivots. The best possible pivot would be the kth largest element itself, since then no further recursive calls would be required. However, QUICKSELECT does not a priori know what the kth largest element is. (Indeed, it is QUICKSELECT's very goal to compute this element.) A more realistic goal might be to choose the median of the list as pivot. This would be a good choice, since then the first and last parts would be the same size, so after each recursive call at least half of the List would be discarded. However, QUICKSELECT does not a priori know what the median is. (Indeed, if k is half the length of the list, then QUICKSELECT's very goal is to compute the median.) A generally bad choice of pivot would be the maximum, since then the last part will generally be much smaller than the first, and (unlessk 1) it is this smaller part which will be discarded. This is where randomness comes in. If QUICKSELECT chooses the pivot randomly then the benefits of good pivots will outweigh the costs of bad pivots. To complete this assignment, you will implement two variants of QUICKSELECT: (1) using one randomly chosen pivor, and (2) using two randomly chosen pivots. Then you will study how many recursive calls your programs make. Because your code will choose the pivots randomly, this number will change each time you run your code. So you will fix an element to select from a fixed list, and run your code many times to determine the average number of recursive calls your programs make. To simplify matters, assume that the input list never contains repeated elements, Here is some partial code for one pivot randomized QUICKSELECT. You will need to fill in the missing parts left as "I...)

Answer 1

Solution:-

pivot = random.int(1,length)

#Put all elements smaller than pivot into l_small and all larger into l_big

for i in range(0, length):
if l[i] < pivot:
l_small.append(l[i])
else:
l_big.append(l[i])