MFC-UNIT2-3.Merge Sort

 

	Merge Sort
1.        1	Merge sort uses which of the following technique to implement sorting? a) backtracking b) greedy algorithm c) divide and conquer d) dynamic programming Answer: c Explanation: Merge sort uses divide and conquer in order to sort a given array. This is because it divides the array into two halves and applies merge sort algorithm to each half individually after which the two sorted halves are merged together.	C
2.        2	What is the average case time complexity of merge sort? a) O(n log n) b) O(n2) c) O(n2 log n) d) O(n log n2) Answer: a Explanation: The recurrence relation for merge sort is given by T(n) = 2T(n/2) + n. It is found to be equal to O(n log n) using the master theorem.	A
3.        3	. What is the auxiliary space complexity of merge sort? a) O(1) b) O(log n) c) O(n) d) O(n log n) Answer: c Explanation: An additional space of O(n) is required in order to merge two sorted arrays. Thus merge sort is not an in place sorting algorithm. .	C
4.        4	Merge sort can be implemented using O(1) auxiliary space. a) true b) false Answer: a Explanation: Standard merge sort requires O(n) space to merge two sorted arrays. We can optimize this merging process so that it takes only constant space. This version is known as in place merge sort.	A
5.        5	What is the worst case time complexity of merge sort? a) O(n log n) b) O(n2) c) O(n2 log n) d) O(n log n2) Answer: a Explanation: The time complexity of merge sort is not affected by worst case as its algorithm has to implement the same number of steps in any case. So its time complexity remains to be O(n log n).	A
6.        6	Which of the following method is used for sorting in merge sort? a) merging b) partitioning c) selection d) exchanging Answer: a Explanation: Merge sort algorithm divides the array into two halves and applies merge sort algorithm to each half individually after which the two sorted halves are merged together. Thus its method of sorting is called merging.	A
7.        7	What will be the best case time complexity of merge sort? a) O(n log n) b) O(n2) c) O(n2 log n) d) O(n log n2) Answer: a Explanation: The time complexity of merge sort is not affected in any case as its algorithm has to implement the same number of steps. So its time complexity remains to be O(n log n) even in the best case.	A
8.        8	Which of the following is not a variant of merge sort? a) in-place merge sort b) bottom up merge sort c) top down merge sort d) linear merge sort Answer: d Explanation: In-place, top down and bottom up merge sort are different variants of merge sort. Whereas linear merge sort is not a possible variant as it is a comparison based sort and the minimum time complexity of any comparison based sort is O(n log n).	D
9.        9	Choose the incorrect statement about merge sort from the following? a) it is a comparison based sort b) it is an adaptive algorithm c) it is not an in place algorithm d) it is stable algorithm Answer: b Explanation: Merge sort is not an adaptive sorting algorithm. This is because it takes O(n log n) time complexity irrespective of any case	B
10.    10	Which of the following is not in place sorting algorithm by default? a) merge sort b) quick sort c) heap sort d) insertion sort Answer: a Explanation: Quick sort, heap sort, and insertion sort are in-place sorting algorithms, whereas an additional space of O(n) is required in order to merge two sorted arrays. Even though we have a variation of merge sort (to do in-place sorting), it is not the default option. So, among the given choices, merge sort is the most appropriate answer.	A
11.    11	Which of the following is not a stable sorting algorithm? a) Quick sort b) Cocktail sort c) Bubble sort d) Merge sort Answer: a Explanation: Out of the given options quick sort is the only algorithm which is not stable. Merge sort is a stable sorting algorithm.	A
12.    12	Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array? a) Quick sort b) Insertion sort c) Selection sort d) Merge sort Answer: d Explanation: Insertion sort takes linear time to sort a partially sorted array. Though merge and quick sort takes O(n*logn) complexity to sort, merge sort is stable. Hence, Merge sort takes less time to sort partially sorted array.	D
13.    13	Merge sort is preferred for arrays over linked lists. a) true b) false Answer: b Explanation: Merge sort is preferred for linked list over arrays. It is because in a linked list the insert operation takes only O(1) time and space which implies that we can implement merge operation in constant time.	B
14.    14	Which of the following sorting algorithm does not use recursion? a) quick sort b) merge sort c) heap sort d) bottom up merge sort Answer: d Explanation: Bottom up merge sort uses the iterative method in order to implement sorting. It begins by merging a pair of adjacent array of size 1 each and then merge arrays of size 2 each in the next step and so on.	D

 

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