a) Trace the quick sort algorithm to sort the list C, O, L, L, E, G, E in alphabetical order. (Unit 1)

b) Discuss Strassen's matrix multiplication and derive its time complexity. (Unit 1)

a) Design merge sort algorithm and discuss its best-case, average-case and worst-case Efficiency. (Unit 1)

b) How to solve the Knapsack problem with greedy method? Explain. (Unit 2)

a) Write an algorithm for single source shortest path and explain with an example. (Unit 2)

b) Discuss briefly about the minimum spanning tree. (Unit 2)

a) What do you mean by forward and backward approach of problem solving in Dynamic Programming? (Unit 3)

b) How the reliability of a system is determined using dynamic programming? Discuss. (Unit 3)

a) Find an optimal solution for following 0/1 Knapsack problem using dynamic programming:
Number of objects $n = 4$, Knapsack Capacity $M = 5$,
Weights $(W_1, W_2, W_3, W_4) = (2, 3, 4, 5)$ and Profits $(P_1, P_2, P_3, P_4) = (3, 4, 5, 6)$. (Unit 3)

b) Explain the 8 queen's problem and apply the backtracking to solve the 8 queen's problem. (Unit 4)

Write the control abstraction for LC-Search. Explain how Traveling Salesperson problem is solved using LCBB.
$$\begin{bmatrix} 0 & 20 & 30 & 10 & 11 \\ 15 & 2 & 16 & 4 & 2 \\ 3 & 5 & 0 & 2 & 4 \\ 10 & 6 & 18 & 0 & 3 \\ 16 & 4 & 7 & 16 & 0 \end{bmatrix}$$ (Unit 4)

a) Discuss the differences between BFS and DFS. (Unit 5)

b) What are 2-3 trees used for? Why are 2-3 trees better than BST trees? Write the limitations of 2-3 tree in CSE. (Unit 5)

Discuss briefly any two of the following:

a) Heap sort (Unit 1)

b) Dynamic Programming (Unit 3)

c) Height balanced tree (Unit 5)

d) Parallel algorithm (Unit 4)