MFC-UNIT-2-2.The Towers of Hanoi

	The Towers of Hanoi
1.        1	What is the objective of tower of hanoi puzzle? a) To move all disks to some other rod by following rules b) To divide the disks equally among the three rods by following rules c) To move all disks to some other rod in random order d) To divide the disks equally among three rods in random order Answer: a Explanation: Objective of tower of hanoi problem is to move all disks to some other rod by following the following rules-1) Only one disk can be moved at a time. 2) Disk can only be moved if it is the uppermost disk of the stack. 3) No disk should be placed over a smaller disk.	A
2.        2	Which of the following is NOT a rule of tower of hanoi puzzle? a) No disk should be placed over a smaller disk b) Disk can only be moved if it is the uppermost disk of the stack c) No disk should be placed over a larger disk d) Only one disk can be moved at a time Answer: c Explanation: The rule is to not put a disk over a smaller one. Putting a smaller disk over larger one is allowed.	C
3.        3	The time complexity of the solution tower of hanoi problem using recursion is _________ a) O(n2) b) O(2n) c) O(n log n) d) O(n) Answer: b Explanation: Time complexity of the problem can be found out by solving the recurrence relation: T(n)=2T(n-1)+c. Result of this relation is found to be equal to 2n. It can be solved using substitution.	B
4.        4	Recurrence equation formed for the tower of hanoi problem is given by _________ a) T(n) = 2T(n-1)+n b) T(n) = 2T(n/2)+c c) T(n) = 2T(n-1)+c d) T(n) = 2T(n/2)+n Answer: c Explanation: As there are 2 recursive calls to n-1 disks and one constant time operation so the recurrence relation will be given by T(n) = 2T(n-1)+c.	C
5.        5	Minimum number of moves required to solve a tower of hanoi problem with n disks is __________ a) 2n b) 2n-1 c) n2 d) n2-1 Answer: b Explanation: Minimum number of moves can be calculated by solving the recurrence relation – T(n)=2T(n-1)+c. Alternatively we can observe the pattern formed by the series of number of moves 1,3,7,15…..Either way it turn out to be equal to 2n-1.	B
6.        6	Space complexity of recursive solution of tower of hanoi puzzle is ________ a) O(1) b) O(n) c) O(log n) d) O(n log n) Answer: b Explanation: Space complexity of tower of hanoi problem can be found out by solving the recurrence relation T(n)=T(n-1)+c. Result of this relation is found out to be n. It can be solved using substitution.	B
7.        7	Which of the following functions correctly represent the solution to tower of hanoi puzzle? a) void ToH(int n,int a,int b,int c) {    If(n>0)    {        ToH(n-1,a,c,b);        cout<<”move a disk from” <<a<<” to”<< c;        ToH(n-1,b,a,c);    } } b) void ToH(int n,int a,int b,int c {    If(n>0)    {        ToH(n-1,a,b,c);        cout<<”move a disk from” <<a<<” to”<< c;        ToH(n-1,b,a,c);    } } c) void ToH(int n,int a,int b,int c) {      If(n>0)      {          ToH(n-1,a,c,b);          cout<<”move a disk from” <<a<<” to”<< c;          ToH(n-1,a,b,c);      } } d) void ToH(int n,int a,int b,int c) {    If(n>0)    {        ToH(n-1,b,a,c);        cout<<”move a disk from” <<a<<” to”<< c;        ToH(n-1,a,c,b);    } }     Answer: a Explanation: The first recursive call moves n-1 disks from a to b using c. Then we move a disk from a to c. Finally the second recursive call moves n-1 disks from b to c using a.	A
8.        8	Recursive solution of tower of hanoi problem is an example of which of the following algorithm? a) Dynamic programming b) Backtracking c) Greedy algorithm d) Divide and conquer Answer: d Explanation: The recursive approach uses divide and conquer algorithm as we break the problem into smaller parts and then solve the smaller parts and finally combine their results to get the overall solution.	D
9.        9	Tower of hanoi problem can be solved iteratively. a) True b) False Answer: a Explanation: Iterative solution to tower of hanoi puzzle also exists. Its approach depends on whether the total numbers of disks are even or odd.	A
1    10	Minimum time required to solve tower of hanoi puzzle with 4 disks assuming one move takes 2 seconds, will be __________ a) 15 seconds b) 30 seconds c) 16 seconds d) 32 seconds Answer: b Explanation: Number of moves = 24-1=16-1=15 Time for 1 move = 2 seconds Time for 15 moves = 15×2 = 30 seconds.	B