CS-402 Analysis Design of Algorithm - Nov 2023 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 \\ T(\sqrt{n}) + C & n > 4 \end{cases}$$
   How to answer

   • Define T(n) with base case n<=4 and recursive case
   • Apply repeated substitution / iteration for sqrt reduction
   • Derive number of levels and closed form O(log log n)
   • State final Theta bound with constant C
2. 7 Marks
   bGive an algorithm for quick sort and analyze the algorithm.
   How to answer

   • Write partition-based quicksort pseudocode
   • Explain divide-and-conquer and pivot placement
   • Analyze best, average and worst-case recurrences
   • State time O(n log n) average, O(n^2) worst and space complexity
3. 7 Marks
   aWhat is the solution generated by the function JS when $n = 7, (P_{1}, P_{2}, P_{3}, ............ P_{7}) = (3, 5, 20, 18, 1, 6, 30)$ and $(d_{1}, d_{2}, ......... d_{7}) = (1, 3, 4, 3, 2, 1, 2)$.
   How to answer

   • Sort jobs by profit descending
   • Iteratively place each job in latest free slot before deadline
   • Compute schedule for n=7 with given P and d
   • State optimal sequence and total profit
4. 7 Marks
   bShow that if $t$ is a spanning tree for the undirected graph $G$, then the addition of an edge $q, q \notin E(t)$ and $q \in E(G)$, to $t$ creates a unique cycle.
   How to answer

   • Define spanning tree t with n-1 edges and connectivity
   • Add non-tree edge q with endpoints already connected in t
   • Show existence of path creating a cycle
   • Prove uniqueness by contradiction using tree acyclicity
5. 7 Marks
   aFind optimal solution for 0/1 knapsack problem $(W_{1}, W_{2}, W_{3}, W_{4}) = (10, 15, 6, 9), (P_{1}, P_{2}, P_{3}, P_{4}) = (2, 5, 8, 1)$ and $M = 30$.
   How to answer

   • Compute profit/weight or enumerate feasible subsets
   • Apply 0/1 knapsack DP / branch-and-bound for M=30
   • Identify optimal subset and max profit
   • State selected items x1..x4
6. 7 Marks
   bHow reliability design can be obtained using dynamic programming?
   How to answer

   • Define reliability design with stage-wise device choices
   • Formulate DP recurrence for max reliability under cost
   • Explain forward/backward recursion and traceback
   • Mention example with multipliers and cost constraint
7. 7 Marks
   aGeneralize Hamiltonian so that it processes a graph whose edges have costs associated with them and finds a Hamiltonian cycle with minimum cost. Assume that all edge costs are positive.
   How to answer

   • Model TSP as minimum-cost Hamiltonian cycle
   • Extend Hamiltonian backtracking with cost bound
   • Add pruning using current best cost and positive edges
   • State algorithm steps and complexity
8. 7 Marks
   bHow can comparison trees be used for deriving lower bounds on problem of sorting.
   How to answer

   • Define comparison tree and decision paths
   • Count leaves n! for sorting permutations
   • Derive height lower bound log(n!) = Omega(n log n)
   • Conclude comparison sort lower bound
9. 7 Marks
   aWrite a function to construct the binary tree with a given inorder sequence I and given postorder sequence P. What is the complexity of the function?
   How to answer

   • Use postorder root as last element to split inorder
   • Give recursive construction pseudocode
   • Analyze recurrence T(n) for skewed/balanced cases
   • State O(n^2) naive and O(n) with hashmap complexity
10. 7 Marks
    bGive an example of an n-vertex graph for which the depth of recursion of DFS starting from a particular vertex V is $n-1$ whereas the queue of BFS has at most one vertex at any given time, if BFS is started from the same vertex V.
    How to answer

    • Give path graph P_n as example
    • Show DFS from endpoint gives recursion depth n-1
    • Show BFS queue holds at most one vertex on path
    • Conclude required depth vs queue behavior
11. 7 Marks
    aWhat do you mean by performance analysis of an algorithm? Explain.
    How to answer

    • Define time/space complexity and performance measures
    • Explain a priori vs a posteriori analysis
    • Discuss asymptotic notations and counting steps
    • Give example of algorithm analysis
12. 7 Marks
    bExplain Heap? Sort the following data using heap sort. 81, 39, 10, 36, 45, 15, 55, 23, 91, 88, 12
    How to answer

    • Define heap and heap property
    • Show build-max-heap steps on given data
    • Perform repeated extract-max to sort
    • List sorted sequence and O(n log n) complexity
13. 7 Marks
    aDraw the portion of state space tree generated by LCBB for following knapsack instance: $n = 4, (P_{1}, P_{2}, P_{3}, P_{4}) = (10, 10, 12, 18)$ and $(W_{1}, W_{2}, W_{3}, W_{4}) = (2, 4, 6, 9)$ and $M = 15$
    How to answer

    • Compute profit densities and LCBB bounds
    • Expand state space tree nodes with bounds
    • Prune infeasible / bounded nodes for M=15
    • Show generated portion and optimal solution
14. 7 Marks
    bGive 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 sets S^i for knapsack DP merging
    • Construct weights causing no dominance pruning
    • Show |S^i| = 2^i for each i <= n
    • Give one instance per n, e.g., powers of 2 weights
15. 14 Marks
    Write short notes on following: (any two)

    1. a)Asymptotic Notations
    2. b)DFS and BFS
    3. c)Graph Coloring Problem
    How to answer

    • Define asymptotic notations / DFS-BFS / graph coloring as applicable
    • Explain key concepts, steps and complexity
    • Give example / diagram for each chosen topic
    • State applications and limitations