Design & Analysis of Algorithms 2025

(a) An algorithm is said to be finite if

1. It uses finite memory
2. It produces correct output
3. It has finite input
4. It terminates after a finite number of steps

(b) In Master's theorem, if $f(n)=\Theta(n^{\log_b a})$ then the solution of the recurrence is

1. $\Theta(f(n))$
2. $\Theta(n\log n)$
3. $\Theta(n^{\log_b a} \log n)$
4. $\Theta(\log n)$

(c) What is the maximum number of swaps that can be performed in the Selection Sort algorithm?

1. $n-1$
2. $n$
3. $1$
4. None of the above

(d) The time complexity of Strassen's Matrix Multiplication is approximately

1. $O(n^3)$
2. $O(n^2)$
3. $O(n^{2.81})$
4. $O(n \log n)$

(e) Which of the following problems cannot be solved optimally by a greedy approach?

1. Minimum Cost Spanning Tree
2. Fractional Knapsack
3. Job Sequencing with Deadlines
4. 0/1 Knapsack

(f) In the Branch-and-Bound approach for the Traveling Salesman Problem (TSP), bounding is used to

1. Find the exact optimal solution immediately
2. Convert TSP into a dynamic programming problem
3. Prune paths that cannot yield better solutions
4. Sort cities by distance

(g) In the Matrix Chain Multiplication problem, the DP table stores

1. The sum of matrix elements
2. Minimum number of scalar multiplications needed for each subchain
3. Maximum determinant of matrix chain
4. Sequence of matrices in ascending order

(h) In 0/1 Knapsack DP solution, the state $K[i][w]$ represents

1. Maximum profit using the first $i$ items for weight limit $w$
2. Total number of items used
3. Minimum weight required to achieve profit $i$
4. Fraction of items included

(i) Topological sorting is applicable to

1. Any graph
2. Directed Acyclic Graph (DAG) only
3. Undirected graphs only
4. Cyclic graphs only

(j) An approximation algorithm guarantees

1. Exact optimal solution
2. Incorrect solution always
3. Random solution without bounds
4. Solution within a known factor of optimal

(a) Solve the following recurrence relations using the Substitution Method:

1. $T(n) = 2T(n/2) + n, T(1) = 1$
2. $T(n) = T(n-1) + n, T(1) = 1$

(b) State and explain the Master's Theorem. Apply it to solve the following recurrence relation: $T(n) = 3T(n/2) + n$

(a) Describe the Merge Sort algorithm with a suitable example. Derive its time complexity using recurrence relations.

(b) Apply the Binary Search algorithm to find the key 41 in the sorted array $[5, 12, 18, 25, 33, 41, 56, 63, 70]$.

Also analyze it's time complexity.

(a) Apply the Heap Sort algorithm to the array $[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]$. Show the initial heap, each deletion step, and the final sorted array. Also analyze the time complexity.

(b) Compare Greedy, Dynamic Programming, and Backtracking approaches with respect to solution strategy, efficiency, and applicability.

(a) A thief has a knapsack of capacity 50 kg. The items available are given below. Apply the Fractional Knapsack Algorithm to select items (or fractions) that maximize total value, and calculate the total weight and total value in the knapsack. Explain why this approach guarantees an optimal solution for the fractional knapsack problem.

Explain why this approach guarantees an optimal solution for the fractional knapsack problem.

(b) Apply Bellman Ford's algorithm step-by-step on the given weighted matrix $W$ to compute single-source shortest paths from node 3. State the time complexity of the algorithm.

(a) Discuss Dijkstra's algorithm in detail with the help of an example. Explain why the algorithm fails for graphs containing negative edge weights. Also, state the time complexity of Dijkstra's algorithm.

(b) Discuss the Dynamic Programming approach for solving the Fibonacci series problem. Explain how it improves efficiency over the recursive method.

(a) Given the distance matrix for 5 cities shown below, apply the Dynamic Programming approach to solve the Travelling Salesman Problem. Find the minimum cost tour starting and ending at City 1 and list the optimal tour. Show the key steps involved in computing the solution.

(b) Given the directed graph $G(V,E)$ with vertices $V=\{1,2,3,4,5\}$ and edges $E=\{(1,2),(1,3),(2,4),(3,4),(4,5)\}$:

1. Represent the graph using an adjacency matrix.
2. Represent the same graph using an adjacency list.

(a) What is a strongly connected component? Find all the strongly connected components in the following graph. Show all necessary steps and data structure values of the algorithm.

(b) What is P, NP, NP-hard, and NP-complete? Write the relationship between all of them.

Write short notes on any two of the following:

(a) Huffman Coding Algorithm

(b) Heuristics

(c) BFS vs DFS

(d) Cook's theorem