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