Design and Analysis of Algorithms - 2025
Mahatma Gandhi Central University, Bihar
B.Tech Computer Science & Engineering
Semester 4 Examination, 2025
Design and Analysis of Algorithms (CSET3127)
Assessment Questions
Design and Analysis of Algorithms (CSET3127) - 2025
Section A (MCQ)
Attempt all the questions. Each question carries one mark.
- 1
Which of the following asymptotic notations represents the tightest bound for an algorithm's running time?
- 2
The recurrence relation for the number of moves required to solve the Tower of Hanoi problem with n disks is:
- 3
Consider the following three claims:
- 4
In Quick Sort algorithm, what is the purpose of choosing a pivot?
- 5
Insertion sort is best suited for which of the following scenarios?
Section B (Short Answer)
Attempt any TWO out of THREE questions. Write briefly in 150 words. Each question carries 2.5 marks.
- 1
What are recurrence relations? How are they used in algorithm analysis?
- 2
What do you understand from Matrix multiplication with the help of divide & conquer approach?
- 3
Explain the θ-notation with the help of suitable diagram for analysing the time complexity.
Section C (Long Answer)
Attempt ALL the questions. Write briefly in 300 words. Each question carries 5 marks.
- 1
Answer any ONE of the following
(a) What do you understand from the divide and conquer paradigm? Write a suitable algorithm for Randomized quick sort.
OR
(b) What are the tree cases of Master’s method? Explain their uses for finding the time complexity of recurrences relations.
- 2
Answer any ONE of the following
(a) Why do we analyse the time complexity of the algorithms in terms of large input size? Explain it with the help of suitable example.
OR
(b) Write down the recurrence relation of Merge sort algorithm and calculate its time complexity with the help of recursion tree method.