Module 2
1. Write a short note on Strassen's matrix multiplication.
2. Give a suitable algorithm to find minimum and maximum element in a list using
divide and conquer approach. Explain the approach with an example (Consider a list
having at least 7 elements). Discuss the time complexity for all cases.
3. Explain Binary search algorithm.
4. Explain quick sort with algorithm and example.
5. Apply Merge sort algorithm to sort the following numbers. Show each step clearly.
10, 5, 7, 6, 1, 4, 8, 3, 2, 9.
6. Find Minimum and Maximum elements of an array X[0:9] = (45, 83, 75, 17, 43, 37,
80, 53, 61, 22) using divide and conquer strategy.
7. Explain the general procedure of divide and conquer method.
8. Explain with example how divide and conquer strategy is used in binary search?
9. Sort the list of the elements 10, 5, 7, 6, 1, 4, 8, 3, 2, 9 using merge sort algorithm and
show its computing time is O(n log n).
10.Write the algorithm and derive the complexity of binary search algorithm.
11.Write algorithm for quick sort. Derive its time complexity.
12.Sort the following numbers using Merge Sort. Also, derive the time complexity of
Merge Sort: 7, 2, 9, 4, 3, 8, 6, 4.
13.Write an algorithm to find the Minimum and Maximum values using divide and
conquer strategy and also derive its complexity.
14.Derive the complexity of quick sort for best case and worst case.
15.Write an algorithm for finding minimum and maximum using divide and conquer.
Also derive its complexity.
16.Write an algorithm for Merge Sort. Derive its time complexity using the substitution
method. Sort the following elements with using Merge Sort: 25, 11, 8, 39, 13, 12.
17.What is the difference between divide and conquer approach and dynamic
programming?
18.Sort the following numbers using Quick Sort. Also, derive the time complexity of
Quick Sort: 50, 31, 71, 38, 77, 81, 12, 33.
19.Write and Explain binary search algorithm.
20.Write an algorithm for quick sort and sort the following elements [40, 11, 4, 72, 17, 2,
49].
21.Explain the Strassen's matrix multiplication concept with an example. Derive its time
complexity.
22.Apply the quick sort algorithm to sort the list. E, X, A, M, P, L, E in alphabetical
order. Analyze the best case, worst case and average case complexities of quick sort.