CS-402 Analysis Design of Algorithm - Dec 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
   aGive the asymptotic bounds for the equation $f(n)=2n_2-4n+20$ and represent it in terms of $\theta$ notation.
   How to answer

   • Define Big-O, Big-Omega and Theta for f(n).
   • Show upper bound f(n) <= c1*n^2 for n >= n0.
   • Show lower bound f(n) >= c2*n^2 for n >= n0.
   • Conclude f(n) = Theta(n^2) with constants.
2. 7 Marks
   bDefine Quicksort? Sort the elements 22, 12, 30, 46, 28, 14, 8, 10, 56, 18, 3 using Merge sort.
   How to answer

   • Define Quicksort principle, partition and recurrence.
   • State Merge sort divide-conquer-merge steps.
   • Show step-wise merging of given 11 elements.
   • Give final sorted sequence and complexity.
3. 7 Marks
   aWrite an algorithm to find the matrix multiplication using Strassen's method.
   How to answer

   • State divide into 4 submatrices A11,A12,A21,A22 and B11... .
   • Give 7 Strassen products M1 to M7 formulas.
   • Give C11,C12,C21,C22 combination formulas.
   • State recurrence T(n)=7T(n/2)+O(n^2) and O(n^log2 7) complexity.
4. 7 Marks
   bConstruct a Huffman coding for the given data? Write the applications of huffman coding.

   

   How to answer

   • Sort characters by frequency and build Huffman tree bottom-up.
   • Assign 0/1 to edges and derive prefix codes.
   • Compute average code length / total bits.
   • List applications: data compression, JPEG, MPEG, text coding.
5. 14 Marks
   Solve the following problem of job sequencing with deadlines using the Greedy method. $n=5$ with profits $(p_1,p_2,p_3,p_4,p_5) = (5, 20, 10, 15, 1)$ and deadlines $(d_1, d_2, d_3, d_4, d_5) = (3, 2, 1, 2, 3)$.
   How to answer

   • Sort jobs by decreasing profit.
   • Check deadline feasibility slot-wise for n=5.
   • Construct feasible sequence and Gantt slots.
   • Compute maximum profit.
6. 7 Marks
   aSolve the following 0/1 Knapsack problem using dynamic programming where $n = 4, m = 40, (w_1,w_2,w_3,w_4) = (2, 11, 22, 15)$ and $(p_1,p_2,p_3,p_4) = (11, 21, 31, 33)$.
   How to answer

   • Formulate 0/1 knapsack DP recurrence f(i,y).
   • Build DP table for n=4, m=40 with given w,p.
   • Trace back to find selected items.
   • State maximum profit and weight used.
7. 7 Marks
   bConstruct a multistage graph for the given graph using the Greedy method.

   

   How to answer

   • Identify stages: S | A,B,C | D,E | T with edge costs.
   • Apply backward/forward greedy for multistage shortest path.
   • Compute cost-to-target at each node.
   • Give minimum cost S-T path.
8. 7 Marks
   aExplain the Floyd Warshall algorithm for the given graph.

   

   How to answer

   • State Floyd-Warshall recurrence D^k[i][j].
   • Initialize distance matrix for 4 nodes with given weights.
   • Iterate k=1 to 4 updating shortest paths.
   • Give final all-pairs shortest path matrix.
9. 7 Marks
   bExplain in detail about the FIFO branch and bound.
   How to answer

   • Define branch and bound and FIFO queue principle.
   • Explain bounding, branching and pruning steps.
   • Give example search tree expansion.
   • State applications and complexity.
10. 7 Marks
    aWrite an algorithm for the 8-queens problem using backtracking.
    How to answer

    • State 8-queens constraints and backtracking idea.
    • Give Place(k,i) / promising function pseudocode.
    • Describe row-by-row placement and backtrack on conflict.
    • State time complexity and solution existence.
11. 7 Marks
    bDraw the state space tree for '$m$' coloring when $n = 3$ and $m = 3$.
    How to answer

    • Define m-coloring and state space tree concept.
    • Draw tree for n=3 nodes with m=3 colors level-wise.
    • Show branching with 3 choices per node.
    • Mention total nodes and chromatic check.
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) = ($double, int, for, if$)$ with $p(1:4) = (3,3,1,1)$ and $q(0:4) = (2,3,1,1)$. Using $r(i,j)$'s construct the optimal binary search tree.
    How to answer

    • Compute w(i,j) from p and q weights.
    • Compute c(i,j) and r(i,j) using OBST recurrence.
    • Fill tables for 0<=i<j<=4.
    • Construct optimal BST from r(0,4) roots.
13. 7 Marks
    bExplain in detail Height balanced tree with an example.
    How to answer

    • Define height-balanced (AVL) condition |hL-hR|<=1.
    • Explain rotations LL, RR, LR, RL with example.
    • Show insertion/deletion with balancing steps.
    • State O(log n) height and operations.
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)Hamiltonian graph and cycle.
    4. d)Breadth First Search.
    How to answer

    • Select any two topics with definition and working.
    • Give algorithm steps / diagram / example for each.
    • State time complexity and applications.
    • Conclude with comparison or use-case.