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 Model Answer:
QS([4, 8, 12, 15, 21, 44], 1, 6) QS([4, 8, 12, 15, 21, 44], 1, 6)
Term 1, 2015
QS([4, 8, 12, 15, 21, 44], 1, 0)
QS([4, 8, 12, 15, 21, 44], 2, 6) QS([4, 8, 12, 15, 21, 44], 2, 6)
QS([4, 8, 12, 15, 21, 44], 2, 1)
QS([4, 8, 12, 15, 21, 44], 3, 6) QS([4, 8, 12, 15, 21, 44], 3, 6)
QS([4, 8, 12, 15, 21, 44], 3, 2)
QS([4, 8, 12, 15, 21, 44], 4, 6) QS([4, 8, 12, 15, 21, 44], 4, 6)
QS([4, 8, 12, 15, 21, 44], 4, 3)
QS([4, 8, 12, 15, 21, 44], 5, 6) QS([4, 8, 12, 15, 21, 44], 5, 6)
QS([4, 8, 12, 15, 21, 44], 5, 4) QS([4, 8, 12, 15, 21, 44], 6, 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.
Model Answer:
SumUp(A, i):
if i = 1 then return ai
else
return ai + SumUp(A, i − 1)
(b) Draw the computation tree that this algorithm would produce when given the sequence (14, 5, 11, 18, 2) as input.
Model Answer:
SumUp((14, 5, 11, 18, 2), 5)
SumUp((14, 5, 11, 18, 2), 4)
SumUp((14, 5, 11, 18, 2), 3)
SumUp((14, 5, 11, 18, 2), 2)
SumUp((14, 5, 11, 18, 2), 1)
(c) Show how the computation tree can be used to explain the running time of
the algorithm.
Model Answer: The computation tree has a depth of Θ(n), and each level of the tree contains just a single node, and the amount of running time asso- ciated with each of these nodes is Θ(1). Thus the total running time for the whole tree is Θ(n).
(d) Express the running time of your algorithm using recurrences.
Program Analysis Model Answer:
Term 1, 2015
T(n) =
(e) Solve the recurrences to find the running time.
Model Answer:
.
= T(n−i)+i·c2 .
= T(n−(n−1))+(n−1)·c2
= T(1)+(n−1)·c2
= c1 +(n−1)·c2
So the running time is Θ(n)
{
c1
T (n − 1) + c2
if n = 1 otherwise
T(n−1)+c2
T(n) =
= [T(n−2)+c2 ]+c2
= T(n−2)+2·c2
= [T(n−3)+c2 ]+2·c2
= T(n−3)+3·c2
Program Analysis Term 1, 2015 3. Analyse the running time of binary search.
Model Answer:
is as follows.
The recurrences for worst-case running time of binary search
Solving the recurrences…
{
T(n) =
c1
T (n/2) + c2
if n = 1 otherwise
T(n) = =
.
= =
T(n/2) + c2 [T(n/22)+c2]+c2
T(n/2⌈logn⌉)+logn·c2 c1 +⌈logn⌉·c2
So the running time in the worst case is O(log n)
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.
Model Answer: The computation is tree is a full binary tree. The height of the tree is n − 1.
(b) Based on analysis of computation trees determine the running time of the algorithm?
Model Answer: Each node is associated with constant running time. There are 2n − 1 nodes in the tree, so the running time is Θ(2n).
(c) Solve the above recurrences to establish the algorithm’s running time.
Model Answer:
2T(n−1)+c
= 22 T(n−2)+21c+20c
T(n) =
= 2 [2T(n−2)+c]+c
[]
= 2 22T(n−3)+c +21c+20c
= 23 T(n−3)+22c+21c+20c
.
= 2n−1 T(1) + 2n−2c + 2n−3c + …21c + 20c
= 2n−1c + 2n−2c + 2n−3c + …21c + 20c n−1
= c∑2i i=0
= c(2n−1)