[SOLVED] Cs5800 – algorithms problem set #3 problem #1 (10 points) play one or more games of “towers of hanoi”, which you can do so on this website:

CS5800 – Algorithms
Problem Set #3
Problem #1 (10 points)
Play one or more games of “Towers of Hanoi”, which you can do so on this website:
https://www.mathsisfun.com/games/towerofhanoi.html
There are three towers, and n disks. Your goal is to move all n disks from Tower 1 to Tower 3, but you
may never place a larger disk on top of a smaller disk.
For example, when n = 3, the game can be solved in 7 moves, which is the optimal result.
(a) Attach a screenshot of you winning the n = 4 game in exactly 15 moves. (No proof or explanation
is necessary – all you need to do is insert a .jpg image, just as I did above.)
(b) Let T(n) be the minimum possible number of moves required to solve the game when there are n
disks. For example, T(2) = 3 and T(3) = 7.
Clearly explain why T(4) = 15, showing it is possible to solve this game in exactly 15 moves
and proving why it is impossible to solve this game in 14 (or fewer) moves.
(c) Find a recurrence relation for T(n) and clearly and carefully explain why that recurrence relation
holds. Then solve the recurrence relation using any method of your choice to determine a formula
for T(n) that is true for all integers n ≥ 1.
(d) Substitute n = log(m) into your recurrence relation for T(n) above, and use the Master Theorem
to prove that T(n) = Θ(2n
). Briefly explain how and why your formula in part (c) is indeed Θ(2n
).

Problem #2 (20 points)
In this question, you will prove the Master Theorem in the special (and most important) situation when
f(n) = n
z
for some real number z.
This result enables us to determine tight asymptotic bounds for various recurrence relations, which
will help us tremendously in algorithm design and algorithm analysis.
If you can reproduce the proof of this result, then you will understand how the Master Theorem works
in all situations – e.g. when f(n) = 4n
3 + 2n
2
log n + 5n + 100 log n + 777. But for the purposes of this
problem, we will assume f(n) = n
z
.
Let x, y, z be real numbers for which T(1) = 1 and T(n) = xT(n/y) + n
z
.
(a) If z < logy(x), prove that T(n) = Θ(n
logy(x)
).
(b) If z = logy(x), prove that T(n) = Θ(n
logy(x)
logy n).
(c) If z > logy(x), prove that T(n) = Θ(n
z
).
(d) Some of you have taken a course in Linear Algebra, a core course in an undergraduate mathematics
curriculum. In this course, students learn how to multiply two n by n matrices, and one can easily
design an algorithm to perform matrix multiplication, running in Θ(n
3
) time.
In 1969, Volker Strassen developed a recursive method to perform matrix multiplication, where
the running time T(n) can be given by the recurrence relation T(n) = 7T(n/2) + n
2
.
Using any of the results in (a), (b), or (c), determine the running time of Strassen’s Algorithm
and show that it is faster than the standard algorithm that runs in Θ(n
3
) time.
Note: if you are unable to prove (a), (b), (c) in its general form, you are welcome to instead solve the
following simplified version of the problem, where you let y = 2 and x = 16, and prove the result for z = 3
in part (a), z = 4 in part (b), and z = 5 in part (c). If your proof is correct, you will be given 10 points
(i.e. instead of the 15 points for the original a,b,c) for solving the simplified version of the problem.