COMP4500/7500 Advanced Algorithms & Data Structures Sample Solution to Tutorial Exercise 6 (2014/2)∗
School of Information Technology and Electrical Engineering, University of Queensland September 2, 2014
1. (Aho, Hopcroft and Ullman, Data Structures and Algorithms, Exercise 10.5)
The number of combinations of m things chosen from amongst a set of n things is denoted C (n, m), for n ≥ 0
and 0 ≤ m ≤ n. We can give a recurrence for C(n, m) as follows: C(n,0) = C(n,n) = 1
C(n,m) = C(n−1,m)+C(n−1,m−1) for0
// we cannot possibly include item i
return SUBSETSUM(i − 1, c) else//s[i]≤c
with = SUBSETSUM(i − 1, c − s[i]) + s[i] without = SUBSETSUM(i − 1, c)
return MAX(with, without)
10
(b) Give a tight bound on the worst-case time complexity of your recursive algorithm. Hint: Consider the case
when c is greater than the sum of the sizes of all the elements in A. Sample solution. If i = 0 then SUBSETSUM takes constant time:
T (0) = Θ(1).
For i > 0, if we assume that c is greater than the sum of the sizes of the first i elements of A, then the last branch of the if is always chosen. That gives the worst case because the last branch contains the same call as the middle branch as well as a second call. The last branch contains two recursive calls with first parameter i − 1, plus statements of constant time complexity. Hence the worst-case time complexity of the above algorithm is captured by the following equation.
T(i)=2T(i−1)+Θ(1) fori>0. We can solve this by iteration as follows:
T(i) = 2T(i−1)+Θ(1) fori≥1
= 2(2T(i−2)+Θ(1))+Θ(1) fori≥2 = 22T(i−2)+2Θ(1)+Θ(1) fori≥2 = 22(2T(i−3)+Θ(1))+2Θ(1)+Θ(1)
= 23T(i−3)+22Θ(1)+2Θ(1)+Θ(1)
fori≥3 fori≥3
.
k−1
= 2kT(i−k)+2jΘ(1).
j=0 Substituting i − k = 0, that is, k = i, in this gives,
fori≥k
i−1 T(i)=2iT(0)+2jΘ(1)=2iΘ(1)+(2i −1)Θ(1)=Θ(2i).
j=0
Hence, the time complexity of above algorithm is Θ(2i).
(c) What is the worst-case space complexity of your recursive algorithm?
Sample solution. The space complexity is determined by the depth of nesting of recursive calls. As a call with parameter i only makes calls with parameter i − 1, the maximum depth of nesting is i. Each call only requires constant space. Hence, the space complexity is Θ(i).
(d) Give a dynamic programming algorithm that matches your recursive algorithm.
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 6 (September 2, 2014) 4
Sample solution. If we examine the calling dependencies in the above procedure, we find that the re- cursive calls on SUBSETSUM have a first argument that is one smaller than i and a second argument that is less than or equal to c. That is SUBSETSUM(i, c) depends on SUBSETSUM(i − 1, c′) for c′ such that 0 ≤ c′ ≤ c. This gives a suitable order for the dynamic programming version of the algorithm. It uses a table ((n + 1) × (C + 1)) of results for the solutions of the subset sum problem. It begins by initialising the table for empty sets to zero.
SUBSETSUM(n, C)
forci=0toC table[0,ci] = 0
fori=1ton forci = 0toC
if s[i] > ci
// Cannot include item i table[i, ci] = table[i − 1, ci]
else
1 2 3 4 5 6 7 8 9
10 11 12 13
Sample solution. The first loop has time complexity
CC Θ(1)=Θ 1 =Θ(C).
ci=0 ci=0
The body of the inner loop of the second loop consists of an if statement that has two branches each of constant time. Hence the worst case of the body of the inner loop is constant time, and the inner loop has time complexity
C
Θ(1) = Θ(C). ci=0
// s[i] ≤ ci
with = table[i − 1, ci − s[i]] + s[i] without = table[i − 1, ci] table[i,ci] = MAX(with,without)
return table[n, C]
(e) What is the worst-case time complexity of your dynamic programming algorithm?
Hence the outer loop has time complexity
nn Θ(C)=Θ C =Θ(n·C). i=1 i=1
Hence the time complexity of the dynamic programming algorithm is Θ(n · C).
(f) What is the worst-case space complexity of your dynamic programming algorithm?
Sample solution. The space requirements for the (n+1) by (C +1) table — assuming dynamic allocation — are Θ(n · C).
(g) Extend your dynamic programming algorithm to return a (there may be more than one) maximal subset. You should add an array R to record whether or not each item is included, i.e., R[i] is TRUE if and only if the ith element is included in the solution.
Hint: Having computed the size of the maximal subsets, start from the nth item and determine whether or not it should be included. The solution is not necessarily unique.
Sample solution. From the recurrence that defines the values in the table we know that if table[i, ci] = table[i − 1, ci − s[i]] + s[i]
then a maximal set can be achieved by including the ith element, and if
COMP4500/7500 (2014) Sample Solution to Tutorial Exercise 6 (September 2, 2014) 5 table[i, ci] = table[i − 1, ci]
then a maximal set can be achieved by excluding the ith element. Note that both these conditions can be true simultaneously, so that there may be more than one maximal set.
The following code can be used to determine a suitable subset with the maximal sum. The code can be inserted in the dynamic programming version of SUBSETSUM just before the final return.
1 ci = table[n, C]
2 fori = ndownto1
3 if table[i, ci] == table[i − 1, ci]
4
5
6 else 7
8
9
// exclude the item R[i] = FALSE
// include the item R[i] = TRUE
ci = ci−s[i]
The extraction of a maximal subset starts by setting ci to the size of the maximal subsets. We have chosen the simpler of the two possible tests. If it is true, the item can be excluded and a maximal set formed from the remaining elements. If it is false, the item must be included to form a maximal set, and the elements (with smaller indices) chosen to be included in the set must have total size ci − s[i].