MIT 6.00 Intro Computer Science (OCW) 81 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
Spectrum: People of QuestionCove, help us make it thrive again!
16 seconds ago 24 Replies 2 Medals
Unicornsandza: lookin for bigbawling wya
50 minutes ago 3 Replies 1 Medal
bigbawling: wheres unicornsandza help
1 hour ago 5 Replies 0 Medals
ExclusiveKylaa: What are 5 things you are grateful for?
1 hour ago 6 Replies 1 Medal
Coyote: I have an ACT coming up... what should I expect?
4 minutes ago 9 Replies 0 Medals
McDonalds: CONGRATS ON PURPLE MY LITTLE RUSSIANud83dude31
1 hour ago 6 Replies 2 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!