||JAI SRI GURUDEV||
Sri AdichunchanagiriShikshana Trust ®
SJB INSTITUTE OF TECHNOLOGY
(Affiliated to VTU, Approved by AICTE - New Delhi, Accredited by NAAC with “A” Grade)
No. 67, BGS Health & Education City, Dr. Vishnuvardhan Road, Kengeri, Bengaluru - 560 060
Department of Computer Science &Engineering
Module 2
Question Bank
Course Name : Design and Analysis of Algorithms
Course Code : 23CST402
Faculty Name : Dr. Krishna A N, Prof. & Head.
Dr. Arun Kumar D R, Asst. Prof
Mrs. Anusha M, Asst.Prof
Design and Analysis of Algorithm
MODULE 2
1. Design an algorithm to sort n numbers using Quick sort . Apply the algorithm for the data 35,
20, 15, 45, 10,60, 15,70. Each time, show the splitting position. [Dec 2019/ Jan 2020, July/
August 2022, Dec 2023/Jan 2024]
2. Discuss the general Divide and conquer method along with control abstraction. Write the
recurrence relation for divide and conquer. [Dec 2019/ Jan 2020, Aug/Sept 2020, Jan/ Feb
2021, July/ August 2022, June/July 2023, Dec 2023/Jan 2024]
3. Write an algorithm to sort the numbers using insertion sort. Discuss its efficiency. [Dec
2023/Jan 2024]
4. Obtain the topological sequence for the following graph using i) Source removal method ii)
DFS based algorithm. [Aug/Sept 2020, Jan/ Feb 2021, July/ August 2022, Jan/ Feb 2023,
Dec 2023/Jan 2024]
2 3 2 5
6 5 4 1 4
3 6
7 1
(a) (b)
a a b
1 2
b c d c d e
3 4
e f g f g
(d) (e)
h i
C1 C4
j C3
( c) C2 C5
(f)
Dept. of CSE, SJBIT Page 1
Design and Analysis of Algorithm
5. Design an algorithm to sort n numbers using merge sort. Write the complexity of merge sort.
[Dec 2019/ Jan 2020, Jan/ Feb 2021, Jan/ Feb 2023, Dec 2023/Jan 2024]
6. Write recursive algorithm to find maximum and minimum element in an array. Construct tree
of recursive call for the data:
a. 22, 13, -5, -8, 15, 60, 17, 31, 47.
b. 31, 22, 12, -7, 75, -6, 17, 47, 60
c. 5, 3, 1, 9, 8, 2, 4, 7.
[Dec 2019/ Jan 2020, Feb/ Mar 2022, July/August 2022, June/July 2023, Dec 2023/Jan 2024]
7. Apply both merge sort and quick sort algorithm to sort the characters
a. VTUBELAGAVI [July/August 2022]
b. ALGORITHM [Jan/ Feb 2021]
8. Apply Strassen’s algorithm for matrix multiplication to multiply the following matrices and
justify how the Starssen’s algorithm is better.
4 3 1 2
(a) [ ] × [ ] [June/July 2019, Feb/Mar 2022, July/August 2022, Jan/
1 2 6 5
Feb 2023, June/July 2023]
𝟏 𝟎 𝟐 𝟏 𝟎 𝟏 𝟎 𝟏
𝟒 𝟏 𝟏 𝟎 𝟐 𝟏 𝟎 𝟒
(b) × [Aug/Sept 2020]
𝟎 𝟏 𝟑 𝟎 𝟐 𝟎 𝟏 𝟏
𝟓 𝟎 𝟐 𝟏 𝟏 𝟑 𝟓 𝟎
9. Compare the straight forward method and divide and conquer method of finding maximum
and minimum elements of the list. [Jan/ Feb 2021]
10. Show the number of elements comparisons with example and show the proof of binary
search time for best, average and worst case analysis. [Dec 2019/ Jan 2020, Jan/ Feb 2021]
11. Demonstrate the applicability of master’s theorem to compute the time complexity of merge
sort. [June/July 2023]
12. Sort the below given array of elements using Quick sort. Mention time complexity
i) 2,6,4,3,9,1,7. [June/July 2023]
ii) 80, 60, 70, 40, 10, 30, 50, 20. [June/July 2019]
iii) 25, 91, 46, 35, 11, 82, 14, 55. [Aug/Sept 2020]
13. What are the advantages and disadvantages of Divide and conquer approach? [Aug/Sept
2020, July/ August 2022, June/July 2023]
14. Discuss Decrease and conquer technique. Explain its variations. [June/July 2023]
15. Sort the below given array of elements using Merge sort. Analyze its time efficiency. Apply
the same to sort
a. 4, 9, 0, -1, 6, 8, 9, 2, 3, 12. [Feb/ Mar 2022]
b. 60, 50, 25, 10, 35, 25, 75, 30. [Dec 2019/ Jan 2020]
c. 67, 90, 12, 56, 23, 34, 45. [Aug/Sept 2020]
Dept. of CSE, SJBIT Page 2
