Question 6 (20%) Consider the Tower of Hanoi problem. There are n disks labeled

Question

Question 6 (20%) Consider the Tower of Hanoi problem. There are n disks labeled 1,23, ..n, and three towers labeled A, B, and C. All disks are initially in tower A and your job is to move them to B with the following constraints. . No disk can be on top of a smaller disk at any time. Only one disk can be moved at a time, and it must be the top disk on the tower Here is an example that demonstrate how to solve this problem using recursion (Hint: Pay attention to steps 0, 3, 4 and 7). Original position Step 4: Move disk 3 from A to B Step 1: Move disk 1 from A to B Step 5: Move disk 1 from C to A Step 2: Move disk 2 from A to C Step 6: Move disk 2 from C to B Step 3: Move disk 1 from B to C Step 7: Move disk 1 from A to B (a) Write a recursive algorithm to solve Tower of Hanoi problem. (10 points) (b) Write the recurrence relation and calculate the running time. (10 points) Note: Do not write Java code. Pseudo code only

Explanation / Answer

Algorithm

There are three towers which are source, destination and aux (only to help moving the disks).

If we have only one disk, then it can easily be moved from source to destination peg.

If we have 2 disks ?

First, we move the smaller (top) disk to aux peg.

Then, we move the larger (bottom) disk to destination peg.

And finally, we move the smaller disk from aux to destination peg.

Now consider the algorithm for Tower of Hanoi with more than two disks.

Algorithm Hanoi(disk, source, dest, aux)

   IF disk == 1, THEN

      move disk from source to dest            

   ELSE

      Hanoi(disk - 1, source, aux, dest)     // Step 1

      move disk from source to dest          // Step 2

      Hanoi(disk - 1, aux, dest, source)     // Step 3

   END IF

Recurrence Relation

The base case - when n is 1. Just just move the single disk directly.

T(1) = 1

In the other cases, three-step procedure. First they move the (n-1)-disk tower to the spare peg; this takes T(n-1) moves. Then move the nth disk, taking 1 move. And finally move the (n-1)-disk tower again, this time on top of the nth disk, taking T(n-1) moves. This gives us our recurrence relation,

T(n) = 2 T(n-1) + 1.

Hence the recurrence relation can be written as

T(n)     =          1                                  if n=1             

            =          2 T(n-1) + 1.               if n>1

Solving the above recurrence

T(n)     =          2T(n-1)+1

            =          2*[2T(n-2)+1]+1

            =          4T(n-2)+3

            =          4*[2T(n-3)+1]+3

            =          8T(n-3)+7

            .

            .

            .

            =          2kT (n-k)+ 2k -1

Let n-k=1

            k=n-1

T(n)     =          2kT (n-k)+ 2k -1

            =          2n-1T (n-(n-1))+ 2n-1 -1

            =          2n-1T (1) + 2n-1 -1

            =          2n-1 -1

            =          O (2n)

           

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.