Ask your own question, for FREE!
MIT 6.00 Intro Computer Science (OCW) 27 Online
OpenStudy (anonymous):

Question about algorithm complexity: "Prove that the recursive solution to the towers of Hanoi problem is optimal. That is, show that any solution requires at least (2^N) - 1 moves." I will add my answer and my question on my second post.

OpenStudy (anonymous):

An algorithm that takes 2^n - 1 moves will have recurrence formula of the form: \[Tn = 2*T(n-1) + 1\] for n >= 2 and \[T(1) = 1\] It's easy to see that this solution holds inductively. Now suppose that\[Tj < Tn\] is a solution that takes less steps than Tn. Through induction, we have that:\[Tj < 2*(2*T(n-2) + 1) + 1\] More generally: \[Tj < 2^k*T(n-k) + 2*k + 1\] For k = n-1, we have: \[Tj < 2^(n-1) + 2*(n-1) + 1\] And I am stuck there. My question is: I am unsure whether or not I correctly assessed the problem. How should I tackle it? It seems like what I did is a very redundant argument. Any ideas? Or better ways to tackle the problem :-)

OpenStudy (anonymous):

I don't know how to do it. But I don't think you can get there from the way you're doing it. 2^n - 1 is the number of steps for the recursive algorithm. They're saying (what you have to prove is) that no solution can take fewer moves than this. Certainly, the absolute minimum any conceivable solution could take is n, because you have to move every piece at least once. So, there might be a solution between n and 2^n - 1. I think usually these kinds of problems are best handled with proof by contradiction. Supposed that there is an algorithm that takes fewer than 2^n - 1 moves, then find some contradiction.

OpenStudy (anonymous):

Thanks mate, you gave me the idea to solve it. At least, I think I solved it now. I was trying to contradict in the recurrence relation, but the better way I found is to prove that \[T(n-1)\] is the least numbers of moves(proof via analysis of the problem) and then prove that \[2^N - 1\] is a solution to the recurrence relation.

Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!
Latest Questions
YoungBlood: STOP THE YELLOW NAME TAG SLANDER!
3 hours ago 11 Replies 2 Medals
Bubblezz: Art for @euphoriiic
5 hours ago 23 Replies 3 Medals
ilovemybf: i need more drawing ideas
7 hours ago 15 Replies 1 Medal
toga: what is a Mayuri
10 hours ago 3 Replies 1 Medal
Midnight97: Here is a beat I made let me know what y'all think
10 hours ago 24 Replies 2 Medals
toga: who thinks that there should be more titles
11 hours ago 5 Replies 0 Medals
Can't find your answer? Make a FREE account and ask your own questions, OR help others and earn volunteer hours!

Join our real-time social learning platform and learn together with your friends!