CS-402 Analysis Design of Algorithm - Jun 2025 Question Paper

Under each question, How to answer lists the points an answer should cover, outlined by CampusPrep from the syllabus. Check the details against your textbook.

1. 7 Marks
   aSolve the following recurrence relations using the substitution method. $$T(n) = \begin{cases} 1 & n \le 4 \\ 2T(\sqrt{n}) + \log n & n > 4 \end{cases}$$
   How to answer

   • State substitution method assumption and unfolding
   • Substitute $T(\sqrt{n})$ repeatedly to get pattern
   • Use base case $n\le 4$ to bound depth $\log\log n$
   • Sum $\log$ terms to obtain closed form / Theta bound
2. 7 Marks
   bThe worst case time of procedure merge sort is O (nlogn). What is its best case time? Can we say that the time for merge sort is O (nlogn)?
   How to answer

   • State worst-case $O(n\log n)$ recurrence for merge sort
   • Argue divide and merge cost is same for best case
   • Conclude best case is also $\Theta(n\log n)$
   • Explain Theta vs O notation for merge sort
3. 7 Marks
   aObtain a set of optimal Huffman codes for message (M1, ... M7) with relative frequencies (q1, q2......,q7) = (4, 5, 7, 8, 10, 12, 20). Draw the decode tree for this set of codes.
   How to answer

   • Sort frequencies (4,5,7,8,10,12,20)
   • Repeatedly merge two smallest to build Huffman tree
   • Assign 0/1 codes and list optimal codes
   • Draw decode tree with M1...M7 as leaves
4. 7 Marks
   bUse algorithm shortest paths to obtain in non-decreasing order the lengths of the shortest paths from vertex 1 to all remaining vertices in the di-graph.

   

   How to answer

   • Initialize Dijkstra distances from vertex 1
   • Iteratively select minimum unvisited vertex
   • Relax outgoing edges using given weights
   • List shortest path lengths in non-decreasing order
5. 7 Marks
   aGive an example of a set of knapsack instances for which $|S^{i}| = 2^{i}, 0 \le i \le n$. The set should include one instance for each $n$.
   How to answer

   • Define S^i sets in knapsack DP
   • Give weight/profit construction causing 2^i distinct sums
   • Show one instance for each n
   • Conclude exponential size
6. 7 Marks
   bExplain Floyd Warshall algorithm with suitable example.
   How to answer

   • State Floyd-Warshall DP recurrence A^k[i][j]
   • Show iteration over intermediate vertex k
   • Work out small example with distance matrices
   • State O(n^3) complexity and path reconstruction
7. 7 Marks
   aGiven an $n \times n$ chessboard, a knight is placed on an arbitrary square with coordinates $(x, y)$. The problem is to determine $n^{2}-1$ Knight moves such that every square of the board is visited once if such a sequence of moves exists. Present an algorithm to solve this problem.
   How to answer

   • Model Knight's tour as Hamiltonian path / backtracking
   • Define legal knight moves and constraints
   • Present recursive backtracking algorithm with Warnsdorff heuristic
   • Discuss termination and complexity
8. 7 Marks
   bConsider the traveling salesperson instance defined by the cost matrix. $$\begin{pmatrix} \infty & 7 & 3 & 12 & 8 \\ 3 & \infty & 6 & 14 & 9 \\ 5 & 8 & \infty & 6 & 18 \\ 9 & 3 & 5 & \infty & 11 \\ 18 & 14 & 9 & 8 & \infty \end{pmatrix}$$
   How to answer

   • State TSP cost matrix with infinite diagonal
   • Apply row/column reduction / branch-and-bound
   • Evaluate tour costs
   • Identify minimum cost tour
9. 7 Marks
   aShow that DFS visits all vertices in G reachable from V.
   How to answer

   • Define DFS discovery from V
   • Use stack/recursion invariant for reachability
   • Show by induction all reachable vertices visited
   • Conclude correctness
10. 7 Marks
    bObtain a nondeterministic algorithm of complexity O($n$) to determine whether there is a subset of $n$ numbers $a_{i}, 1 \le i \le n$, that sums of $m$.
    How to answer

    • Nondeterministically guess subset indices
    • Sum chosen a_i in O(n) time
    • Compare sum to m for acceptance
    • Argue O(n) complexity on nondeterministic machine
11. 7 Marks
    aWrite an algorithm to delete an element $x$ from a binary search tree $t$. What is the time complexity of your algorithm?
    How to answer

    • Search for x and handle not-found case
    • Handle leaf, one-child and two-children cases
    • Replace with inorder successor/predecessor when needed
    • Analyze O(h) worst-case, O(log n) average
12. 7 Marks
    bWhat do you mean by balance factor in AVL tree? Give a suitable example to balance a AVL tree.
    How to answer

    • Define balance factor = height(left)-height(right)
    • List allowed values -1,0,1 and rotations
    • Show insertion causing imbalance example
    • Apply LL/RR/LR/RL rotation to rebalance
13. 7 Marks
    aSuppose there are $n$ jobs to be executed but only $k$ processors that can work in parallel. The time required by jobs $i$ to $t_{i}$, write an algorithm that determines which jobs are to be run on which processors and the order in which they should be run so that the finish time of the last job is minimized.
    How to answer

    • Sort jobs / use min-heap of processor loads
    • Assign each job to earliest free processor
    • Track finish times to minimize makespan
    • State greedy / list scheduling complexity
14. 7 Marks
    bFind optimal solution for 0/1 knapsack problem (W1, W2, W3, W4) = (10, 15, 6, 9), (P1, P2, P3, P4) = (2, 5, 8, 1) and M = 30.
    How to answer

    • Compute profit/weight ratios or DP table for M=30
    • Evaluate feasible subsets of 4 items
    • Select max profit feasible set
    • State optimal vector and profit
15. 14 Marks
    Write short notes on following. (any two)

    1. a)B-Trees
    2. b)Tree Traversal
    3. c)Reliability Design
    How to answer

    • Define B-Trees / Tree Traversal / Reliability Design
    • Explain key properties and use cases
    • Give diagram/example for each chosen topic
    • Summarize advantages