Program Analysis Problem Sheet 8
1. This question is concerned with the QuickSort algorithm.
QS(A, i, j) :
if j > i
k ← Partition(A, i, j) QS(A, i, k − 1) QS(A, k + 1, j)
Term 1, 2015
Partition(A, i, j) returns position k and permutes the elements of the subsequence A[i..j] such that A[k] holds the value that was previously held in A[i] and for all p such that i ≤ p ≤ j, if p ≥ k then A[p] ≥ A[k] and if p ≤ k then A[p] ≤ A[k].
Draw the computation tree that the QS algorithm would produce for the input [4, 8, 12, 15, 21, 44]. Assume that the pivot is chosen to be the leftmost value in the sequence under consideration. At each node in the computation tree show the call to QS, as well as the result of partitioning the array (prior to making the recursive calls. In other words, the root of the computation tree could be labelled as follows:
QS([4, 8, 12, 15, 21, 44], 1, 6) QS([4, 8, 12, 15, 21, 44], 1, 6)
Program Analysis Term 1, 2015
2.
(a) Write a recursive algorithm that sums up the numbers held in a sequence A = (a1, . . . , an). You will need to include a parameter that specifies which subsequence of the sequence is under consideration for a particular recur- sive call to the algorithm.
(b) Draw the computation tree that this algorithm would produce when given the sequence (14, 5, 11, 18, 2) as input.
(c) Show how the computation tree can be used to explain the running time of the algorithm.
(d) Express the running time of your algorithm using recurrences. (e) Solve the recurrences to find the running time.
Program Analysis Term 1, 2015 3. Analyse the running time of binary search.
Program Analysis Term 1, 2015 4. Consider an algorithm with a running time given by the following recurrences.
{
T(n) =
c if n = 1 2T (n − 1) + c otherwise
(a) Describe the characteristics of the general form of a computation tree for the algorithm, including the height as a function of n. The height of the tree is the length of the longest path from the root to a leaf node.
(b) Based on analysis of computation trees determine the running time of the algorithm?
(c) Solve the above recurrences to establish the algorithm’s running time.