Question 3 [12 marks]
Recall the deterministic quicksort algorithm we saw in class:
Now consider array A below, which contains the elements a through z and A through Z each exactly
once in a random order:
A = [o, j, g, B, v, i, k, w, …(remainder of array not shown)]
The ordering relationship between the elements is based on their alphabetical rank, so a < b < c < .... < z < A < B < C < D < ..... < Z. For each question below, provide a numeric answer. Justify that answer and explain the reasoning behind any formulae you apply. No explanation means no marks. Your must simplify your answer as much as possible so that it is a numeric value. (a) If we run deterministic quicksort on A, how many times will the element with value g be compared to the element with value k? (b) If we run deterministic quicksort on A, what will be the pivot in the first recursive call to quicksort(bigger) from line 8? (c) During the entire execution of deterministic quicksort on A, how many times will the element that you just answered in part (b) above be compared to another element in line 15? (d) If we run randomized quicksort on A, what is the probability that after the first execution of line 6 (before any recursive calls), bigger will have a length less than 6? Round your answer to three decimal points and explain how you derived it. (e) If we run randomized quicksort on A, what is the probability that h is chosen as the pivot in the first recursive call to quicksort(bigger)? (f) When we run randomized quicksort on A, what is the expected number of element comparisons (in line 15) that will be done in the first call to partition in the first recursive call to quicksort(smaller)? (g) If we run randomized quicksort on A, what is the probability that the element with value g will be compared to the element with value k at any point during the execution of the algorithm? 1