CS-402 Analysis Design of Algorithm - Jun 2024 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
   aObtain the asymptotic bound using the substitution method for the recurrence relation $T(n) = 3T(n/3) + n$ and represent it in terms of $\theta$ notation.
   How to answer

   • Assume $T(n) \le c n \log n$ (or $c n \log_3 n$) for substitution
   • Substitute into $T(n)=3T(n/3)+n$ and simplify
   • Choose c large enough to satisfy base case and inductive step
   • Conclude $T(n)=\Theta(n \log n)$
2. 7 Marks
   bWhat is Merge sort? Sort the elements 20, 30, 15, 11, 35, 19, 12, 11, 55 using Merge sort.
   How to answer

   • Define Merge sort divide-and-conquer and merge procedure
   • Show recursive splitting of given list
   • Show merging steps in sorted order
   • Give final sorted list and $O(n \log n)$ complexity
3. 7 Marks
   aDiscuss Strassen's matrix multiplication and Classical $O(n^2)$ methods. Determine when Strassen's method outperforms classical method.
   How to answer

   • State classical $O(n^3)$ matrix multiplication
   • State Strassen's 7 multiplications and $T(n)=7T(n/2)+O(n^2)$
   • Compare $O(n^{\log_2 7}) \approx O(n^{2.81})$ vs $O(n^3)$
   • Discuss crossover point, constants and when Strassen wins
4. 7 Marks
   bDefine spanning tree? Construct a minimal spanning tree for the given graph using Prim's algorithm.

   

   How to answer

   • Define spanning tree and minimal spanning tree
   • State Prim's algorithm steps starting from a vertex
   • Show edge selection steps on given 6-node graph
   • Give final MST and its total weight
5. 14 Marks
   Solve the following problem of job sequencing with deadlines using the Greedy method. $n = 4$, $(p_1, p_2, p_3, p_4) = (100, 10, 15, 27)$ and $(d_1, d_2, d_3, d_4) = (2, 1, 2, 1)$.
   How to answer

   • Sort jobs by profit descending
   • Check deadline feasibility using slots
   • Construct feasible sequence
   • Compute maximum profit
6. 7 Marks
   aApply the greedy method to solve the 0/1 Knapsack problem for $n = 3$, $m = 20$, $(w_1, w_2, w_3) = (18, 15, 10)$ and $(p_1, p_2, p_3) = (25, 24, 15)$.
   How to answer

   • Compute profit/weight ratios
   • State greedy selection order for 0/1 knapsack
   • Check capacity $m=20$ feasibility
   • Give selected items and total profit/weight
7. 7 Marks
   bConstruct a multistage graph for the given graph using the greedy method.

   

   How to answer

   • Define multistage graph and stages
   • Apply forward/backward greedy for shortest path
   • Evaluate stage-wise costs on given 12-node graph
   • Give minimum cost path from 1 to 12
8. 7 Marks
   aExplain the Floyd Warshall algorithm for the given graph.

   

   How to answer

   • State Floyd-Warshall recurrence $D^{(k)}$
   • Initialize distance matrix for 4-node graph
   • Show iterations for k=1 to 4
   • Give all-pairs shortest paths
9. 7 Marks
   bUsing branch and bound technique explain the 0/1 knapsack problem.
   How to answer

   • Define 0/1 knapsack and bounding function
   • Explain branching and upper bound calculation
   • Show state-space tree pruning
   • Give optimal solution
10. 7 Marks
    aGive the solution to the 8-queens problem using backtracking.
    How to answer

    • State 8-queens constraints and backtracking idea
    • Show placement row by row with backtrack
    • Give one valid board configuration
    • Mention time complexity
11. 7 Marks
    bWhat is graph coloring? Explain graph coloring for the given graph.

    

    How to answer

    • Define graph coloring and chromatic number
    • State coloring rules/constraints
    • Color given graph with vertices a,b,c,d,e,f
    • Give minimum number of colors needed
12. 7 Marks
    aUse the function OBST to compute $w(i, j)$, $r(i, j)$ and $c(i, j)$, $0 \le i < j \le 4$ for the identifier set $(a_1, a_2, a_3, a_4) =$ (char, float, while, else) with $p(1) = \frac{1}{20}$, $p(2) = \frac{1}{5}$, $p(3) = \frac{1}{10}$, $p(4) = \frac{1}{20}$, $q(0) = \frac{1}{5}$, $q(1) = \frac{1}{10}$, $q(2) = \frac{1}{5}$, $q(4) = \frac{1}{20}$. Using $r(i, j)$'s construct the optimal binary search tree.
    How to answer

    • Compute $w(i,j)$ from p and q
    • Compute $c(i,j)$ and $r(i,j)$ using OBST recurrence
    • Fill tables for $0\le i<j\le 4$
    • Construct optimal BST from $r(0,4)$
13. 7 Marks
    bExplain in detail about 2-3 Trees with an example.
    How to answer

    • Define 2-3 tree properties (2-node, 3-node)
    • Explain search, insert, split operations
    • Give example with step-by-step insertion
    • Mention balanced height and complexity
14. 14 Marks
    Write short notes on any two of the following :

    1. a)Binary search algorithm and its time complexity
    2. b)Single source shortest path algorithm
    3. c)Parallel algorithms
    4. d)NP Completeness
    How to answer

    • For each chosen topic give definition and principle
    • Give algorithm steps/pseudocode
    • Give example and complexity analysis
    • Conclude with applications