Algorithm design problem set
LE/EECS3101: Design and Analysis of Algorithms
Tutorial 2: Runtime Analysis - Solution
1. Compute the running time of the following program for matrix multi- plication.
1 fun m a t r i x M u l t (A [ 1 . . n ] [ 1 . . n ] , B [ 1 . . n ] [ 1 . . n ] ) 2 for i = 1 to n 3 for j = 1 to n 4 S [ i , j ] = 0 5 for k = 1 to n 6 S [ i , j ] = S [ i , j ] + A [ i , k ] ∗ B [ k , j ] 7 return S
Solution: We can do an analysis like we did in class. Note that the first line of each loop is executed once more than the body of the loop, as ex- plained in class. Since all the loop indices run from 1 to n, the number of times each line is executed can be written by inspection. The expressions are in the table below.
Line number Cost Number of executions
1 0 1
2 c1 n+1
3 c2 n(n + 1)
4 c3 n 2
5 c4 n 2(n + 1)
6 c5 n 3
7 c6 1
Adding up the total cost we get an expression of the form An3+Bn2+Cn+D, where A, B, C, D are positive constants. Then we show that the cost is Θ(n3).
1
2. What is the value returned by the following code? What is a tight bound on its running time? Justify your answer.
1 fun someFun ( n ) 2 s = 2 3 for i = 1 to n 4 for j = 1 to n 5 s = s ∗ s 6 return s
Solution: Since s is initially 2 and gets squared each time line 5 is ex- ecuted, the final value of s is 22
k , where k is the number of times line 5
executes. Line 5 executes n2 times, so the return value is 22 n2
.
The running time is Θ(n2), because of the nested loops.
3. What is the value returned by the following code? Give a tight bound on the running time of the algorithm. Justify your answer. Assume that return terminates the method, even if it is executed inside a loop.
1 fun evenMoreFun ( n ) 2 s = 2 3 for i = 1 to n 4 for j = 1 to n 5 i f ( i+j > n +1) 6 return s 7 s = s ∗ s 8 return s
Solution: In this case, line 5 executes 2n times for i = 1, 2, j = 1, . . . n but in the last of these times i = 2, j = n, the test on line 5 is true and line 6 is executed, terminating the execution. So line 7 runs k = 2n − 1 times. So the return value is 22
2n−1 .
The running time is Θ(n) since the outer loop only runs for i = 1, 2.
4. The Tower of Hanoi is mathematical puzzle where the goal is to move a stack of n discs, one at a time, from one rode to another. At no point in time should a larger disk be placed on top of a smaller one. Design a Divide and Conquer algorithm to solve the Tower of Hanoi Problem for n disks. Give a tight bound on the running time of your algorithm and prove your answer.
2
Source: wikimedia.org - Creative Commons License
Solution:
1 fun h a n o i ( n , from , to , i n t e r m e d i a r y ) 2 i f n == 0 3 return 4 h a n o i ( n−1 , from , i n t e r m e d i a r y , to ) 5 h a n o i ( n−1 , i n t e r m e d i a r y , to , from )
Let T (n) be the number of steps needed to solve the puzzle for n disks. We get the following recurrence relation:
T (n) = 2T (n − 1) + 1
Let’s look at the first few values:
1. T(1) = 1
2. T(2) = 3
3. T(3) = 7
4. T(4) = 15
It looks like T (n) = 2n − 1. If we have a good guess, we can check by plugging it into the recurrence relation to prove it:
T (n) = 2T (n − 1) + 1 = 2(2n−1 − 1) + 1 = 2n − 2 + 1 = 2n − 1
3
Looks like our guess is right! T (n) = 2n − 1. We can also prove it by substitution:
T (n) = 2T (n − 1) + 1 = 2(2T (n − 2) + 1) + 1 = 2(2(2T (n − 3) + 1) + 1) + 1 = ...
= 2iT (n − i) + 2i−1 + 2i−2 + ... + 1
We need to replace T (n − i) with the base case T (1). So n − i = 1, i.e., i = n − 1:
T (n) = 2n−1 + 2n−2 + 2n−3 + ... + 1
= n−1∑ j=0
2j
= 2n − 1
4