Module-2: Divide and Conquer
Module
Review Questions
Sl.
Questions Marks Exam
No.
General Method, Solving Recurrence equations
1 Explain the general concept of divide and conquer method. Give the 5 Jul 19,
general algorithm DAndC(P) [ Where P is the problem to solve] to Jul 18,
illustrate this technique. Jul 17
Discuss general divide and conquer technique with
ith control abstraction
and recurrence relation.
2 List the advantages and disadvantages of Divide and Conquer. 4 Jul 17
3 Find the upper bound of recurrences given below by substitution method. 8
i) T(n) = 2 T(n/2)+n ii) T(n) = T(n/2) + 1
4 Explain the general method of substitution method to solve the 6
recurrence equation.
5 State and explain master theorem to solve the recurrence equation. 5
6 Consider Tower of Hanoi puzzle. Derive the recurrence relation for the 6
total movement of disk. Solve the recurrence relation using substitution
method
Binary Search, Max and Min
7 Show how binary search problem can be solved using the divide and 6 Jul 17,
conquer method. Write an algorithm for binary search and find average Jul 19,
case efficiency. Jan 20
8 Design an algorithm to find the maximum and minimum element in a 8 Jan 18
given list of n numbers using divide and conquer method. Jul 18
Merge Sort, Quick Sort
9 Write the algorithm for Merge Sort.
Sort Illustrate with an example. Derive the 8 Jul 18
time efficiency (best case, average case, worst case) of the algorithm. Jan 19
Jul 19
Sort the following elements using merge sort. Write the recursion tree.
10
70, 20, 30, 40, 10, 50, 60
Alternatively:: Use D & C method to sort the numbers which divides
problem size by considering position
Prepared by Harivinod N [Link] Page| 1
11 Write algorithm for Merge Sort and Trace 60, 50, 25, 10, 35, 25, 75, 30. Jan 20
12 Write an algorithm for sorting the numbers using Quick sort. Derive the 8 Jan 19,
best case, worst case, average case time efficiency of the algorithm. Jul 19,
Jan 20
13 Discuss how quick-sort works to sort an array and trace for the following 8 Jul 18
dataset. Draw the tree of recursive calls made.
Jan 19
65, 70, 75, 80, 85,60, 55, 50, 45
14 Illustrate the tracing of quick sort algorithm for the following set of 8 Jul 17
numbers: 25, 10, 72, l8, 40, 11, 64, 58, 32, 9
15 Sort the list E, X, A, M, P, L, E in alphabetical order using the Quick Sort 8 Jan 18
algorithm. Draw the tree of recursive call.
16 Trace the quicksort algorithm for following list in ascending order 8 Jul 19
80, 60, 70, 40, 10, 30, 50, 20
Stressen’sMatrix Multiplication
17 Explain the algorithm which is used to perform matrix multiplication in an 8 Jan 18
efficient way. OR
Jan 19
Briefly explain Strassen's matrix multiplication and how its uses divide and
conquer method. Obtain the time complexity.
18 Apply Strassen's matrix multiplication to multiply following matrices. 8 Jul 19
Discussmethod is better than directmatrix multiplication method.
Decrease and Conquer, Topological Sorting
19 What are the three major variations of decrease and conquer technique? 6 Jan 19
Explain with an example for each.
20 Explain topological sorting with example. 6 Jan 20
21 Apply source removal method to obtain topological sort for the given 6 Jul 18
graph.
Prepared by Harivinod N [Link] Page| 2
22 Illustrate the topological sorting for the following graph. 6 Jul 17
23 Apply DFS for below graph to solve to topological sorting. 6 Jan 20
24 Apply DFS for below graph to solve to topological sorting. 6 Jul 19
Prepared by Harivinod N [Link] Page| 3