Consider the following variant for the Tower of Hanoi problem. Suppose there are four needles A,...

   

Transcribed Image Text:

Consider the following variant for the Tower of Hanoi problem. Suppose there are four needles A, B, C, D. Initially all n disks are at A and they have to be moved such that the top n/2 end up at C and the bottom n/2 end up at D. There are two limitations however: No larger disk can be on top of a smaller one. . With the exception of the needle at A, no other needle can have more that n/2 disks at any time. a) (7 points) Describe an algorithm that solves the tower of Hanoi problem in this case. Give the pseudocode of the algorithm b) (3 points) Argue about the algorithm's correctness. e) (5 points) Analyze its running time. How many steps are required now to move then disks from A to C and D? Hint: You may use the algorithm described in class for the 3 needles problem... Consider the following variant for the Tower of Hanoi problem. Suppose there are four needles A, B, C, D. Initially all n disks are at A and they have to be moved such that the top n/2 end up at C and the bottom n/2 end up at D. There are two limitations however: No larger disk can be on top of a smaller one. . With the exception of the needle at A, no other needle can have more that n/2 disks at any time. a) (7 points) Describe an algorithm that solves the tower of Hanoi problem in this case. Give the pseudocode of the algorithm b) (3 points) Argue about the algorithm's correctness. e) (5 points) Analyze its running time. How many steps are required now to move then disks from A to C and D? Hint: You may use the algorithm described in class for the 3 needles problem...

Answer rating: 100% (QA)

The image contains a question about a variant of the Tower of Hanoi problem involving four needles instead of the traditional three The needles are named A B C and D and there are two constraints spec... View the full answer