CY-502 Design And Analysis of Algorithms - 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
   aShow that the average case time complexity of binary search is $O(\log n)$.
   How to answer

   • Define binary search on sorted array of size n with mid comparison.
   • Average case: assume successful search with uniform probability 1/n for each position.
   • Derive average number of comparisons using decision tree / summation over levels.
   • Show average comparisons ~ log n - O(1) hence Theta(log n) i.e. O(log n).
2. 7 Marks
   bDefine time Complexity. Describe different notations used to represent these complexities.
   How to answer

   • Define time complexity as function of input size measuring running time.
   • Introduce need for asymptotic analysis and worst/average/best case.
   • Describe Big-O, Omega, Theta notations with definitions.
   • Give examples and graphical interpretation of notations.
3. 7 Marks
   aExplain quick sort algorithm and sort the following list of number using quick sort algorithm. $A = \{6, 15, 3, 14, 25, 36, 18\}$.
   How to answer

   • Explain divide-and-conquer, partition and pivot choice in quick sort.
   • Give quick sort algorithm / pseudocode and partition procedure.
   • Trace partitioning steps on $A = \{6,15,3,14,25,36,18\}$.
   • Show recursive sorting and final sorted list with complexity.
4. 7 Marks
   bWrite and solve recurrence relation for Strassen's matrix multiplication.
   How to answer

   • Describe Strassen's 7 multiplications vs 8 in standard divide-and-conquer.
   • Write recurrence $T(n) = 7T(n/2) + O(n^2)$.
   • Solve by Master theorem / recursion tree / substitution.
   • Conclude $T(n) = O(n^{\log_2 7}) \approx O(n^{2.81})$.
5. 7 Marks
   aCompute the optimal solution for knapsack problem using greedy method $n = 4$, $m = 15$, $(p_1, p_2, p_3, p_4) = (10, 10, 12, 18)$, $(w_1, w_2, w_3, w_4) = (2, 4, 6, 9)$.
   How to answer

   • Compute profit/weight ratios $p_i/w_i$ and sort in decreasing order.
   • Fill knapsack capacity $m=15$ greedily including fractions.
   • Compute selection vector $x_i$ and total profit.
   • State optimal solution and greedy complexity $O(n \log n)$.
6. 7 Marks
   bExplain prism algorithm. Find its complexity.
   How to answer

   • Describe Prim's (printed as prism) MST algorithm and cut property.
   • Give pseudocode using min-key / priority queue.
   • Trace growth of MST from arbitrary start vertex.
   • State time complexity $O(E \log V)$ with heap, $O(V^2)$ naive.
7. 7 Marks
   aDescribe in detail job sequencing with deadlines problem. Let $n = 6$, $p = (200, 180, 190, 300, 120, 100)$, $d = (5, 3, 3, 2, 4, 2)$. Find the optimal solution for the given values.
   How to answer

   • Define job sequencing with deadlines, profits $p_i$ and deadlines $d_i$.
   • Explain greedy ordering by profit and feasible slot assignment.
   • Apply to $n=6$, $p=(200,180,190,300,120,100)$, $d=(5,3,3,2,4,2)$ step by step.
   • Give optimal sequence, total profit and complexity.
8. 7 Marks
   bDifferentiate between dynamic programming and divide and conquer.
   How to answer

   • Define divide and conquer: divide, conquer, combine with independent subproblems.
   • Define dynamic programming: overlapping subproblems and optimal substructure with memoization.
   • Compare on criteria: subproblem overlap, recursion vs table, examples.
   • Conclude when to use each with examples like merge sort vs knapsack.
9. 7 Marks
   aWhat is multistage graph problem. Discuss its solution based on dynamic programming approach.
   How to answer

   • Define multistage graph and stages, source to sink shortest path.
   • Formulate forward/backward recurrence $cost(i,j)$.
   • Explain DP algorithm steps and complexity $O(V+E)$.
   • Give example trace of minimum-cost path.
10. 7 Marks
    bExplain optimal merge (pattern) in brief.
    How to answer

    • Define optimal merge pattern for merging sorted files.
    • Explain greedy using min-heap / Huffman-like merging.
    • Give algorithm steps and example cost calculation.
    • State complexity $O(n \log n)$.
11. 7 Marks
    aExplain 8 queen problem and write an algorithm using backtracking to solve this problem.
    How to answer

    • State 8-queen problem: place 8 non-attacking queens on 8x8 board.
    • Explain backtracking with promising function and bounding.
    • Give NQueens algorithm / pseudocode with Place function.
    • Illustrate solution vector and state-space tree.
12. 7 Marks
    bExplain the general method of branch and bound.
    How to answer

    • Define branch and bound and live, E- and dead nodes.
    • Explain LC-search, FIFO, LIFO branching and bounding function.
    • Describe general steps with state-space tree pruning.
    • Give examples like TSP, knapsack, 15-puzzle.
13. 7 Marks
    aCompare NP-hard and NP-completeness.
    How to answer

    • Define NP, NP-hard and NP-complete classes.
    • Compare on basis of definition, reducibility, solvability.
    • Give examples: SAT, TSP, clique for NP-complete.
    • Present in tabular comparison with Venn diagram.
14. 7 Marks
    bDesign Horner's algorithm to evaluate a polynomial.
    How to answer

    • State polynomial evaluation problem $P(x)=a_nx^n+...+a_0$.
    • Derive Horner's rule $P(x)=(...((a_nx+a_{n-1})x+...)x+a_0)$.
    • Give Horner algorithm pseudocode and trace.
    • Show complexity $O(n)$ multiplications vs $O(n^2)$ naive.
15. 14 Marks
    Write short notes on any two of the following:

    1. a)Parallel Algorithm
    2. b)Huffman Coding
    3. c)Space Complexity
    4. d)Traveling Sales Person Problem
    How to answer

    • Select any two topics from the four options.
    • For each: give definition, working principle and steps.
    • Include formula / algorithm / example and applications.
    • Mention complexities and diagram where relevant.