Released Jan 27, 2020 Deadline Feb 14, 2020
• Submit your solutions to the convenor directly during classes, or to the department office at the College House.
• Do not write your name on your submissions, just your student number / userid.
• You must submit a completed “Cover sheet for coursework” available from the module webpage.
• Explanations on marking criteria can be found on the module webpage.
1. Consider the following pseudocode. Assume arrays are zero-based.
f(A, i, j) {
print("f", i, j);
n := j-i+1;
mid := floor((i+j)/2);
if (n>1) {
f(A, i, mid);
f(A, mid+1, j);
g(A, i, j);
}
}
g(A, i, j) {
print("g", i, j);
n := j-i+1;
if (n == 2) {
if (A[i] > A[j]) swap A[i] and A[j];
}
else {
for(k := 0 to n/4-1) swap A[i+n/4+k] with A[i+n/2+k];
// swap 2nd and 3rd quarters
g(A, i, i+n/2-1); // recurse on 1st and 2nd quarters
g(A, i+n/2, j); // recurse on 3rd and 4th quarters
g(A, i+n/4, i+3n/4-1); // recurse on 2nd and 3rd quarters
}
}
The print() function prints a line containing the string and the values of the two arguments. For example, when f(A,0,7) is called, it prints a line f 0 7.
(a) Suppose initially A = [4, 2, 3, 1] and f(A, 0, 3) is called. Write down all the printouts made, in the correct order they are printed. Also, write down the final contents of A, and briefly explain how you obtained your answer. [10 marks]
(b) Write down a recurrence formula for the time complexity of g(). Solve the recurrence. For full credit do not use the Master Theorem. [15 marks]
(c) Write do wn a recurrence formula for the time complexity of f(). Solve the recurrence. (You can use the Master Theorem.) [10 marks]
2. In this question we consider a modified quicksort algorithm to sort an array A[1..n]. It chooses two elements of the array, A[1] and A[n], as pivots. Let x and y (x ≤ y) be the values of the chosen pivots. Then a modified partition procedure is used to partition A so that the array is separated into three parts by the two pivots, i.e.: A[1..q 1 −1] contain elements less than or equal to x; A[q 1 ] is x; A[q 1 + 1..q 2 − 1] contain elements larger than x and at most y; A[q 2 ] is y; and A[q 2 + 1..n] contain elements larger than y. Finally the three subarrays are sorted recursively.
(a) Give the pseudocode of such a modified partition procedure. In addition to partitioning, it should also return the two partition points q 1 and q 2 . The procedure should be ‘in-place’ (i.e. no copying to another array) and runs in O(n) time. [10 marks]
(b) Give the pseudocode of the modified quicksort. [5 marks]
(c) Suppose the three subarrays are always of the same size. Analyse the time complexity of this modified quicksort. [10 marks]
(d) What is the worst-case time complexity of this modified quicksort? Explain your answer. [10 marks]
3. You are given two series of data points X[1..n] and Y [1..n], where n ≥ 2. It is known that X[1] > Y [1] and X[n] < Y [n]; in other words, the Y series is initially below the X series but will eventually ‘overtake’ the X series. We want to find one such overtaking point, i.e., a value k where X[k−1] ≥ Y [k−1] but X[k] < Y [k]. Note that there could be many overtaking points; you are only required to report any one of them.
(a) One obvious algorithm is keep checking whether X[i] ≥ Y [i] for i = 1,2,... until it is not true. What is the worst-case time complexity of this algorithm? [5 marks]
(b) Give an O(logn) time algorithm for this problem. Prove the time complexity of your algorithm. You can assume n is a power of 2.
(You can use without proof the fact that an overtaking point must exist within a region [p..r] if X[p] ≥ Y [p] and X[r] < Y [r].) [15 marks]
(c) Prove an Ω(logn) lower bound on the time complexity of any comparison-based algorithm for this problem. [10 marks]