CY-502 Design And Analysis of Algorithms - Nov 2022 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 quick sort is $O(n \log n)$
   How to answer

   • Define quicksort partition and recurrence for average case
   • Assume all permutations equally likely, partition position probabilities
   • Set up average-case recurrence T(n) = (n-1) + (2/n) sum_{k} T(k)
   • Solve recurrence by substitution/induction to get O(n log n)
   • Conclude average complexity Theta(n log n)
2. 7 Marks
   bWrite and solve recurrence relation for Strassen's matrix multiplication
   How to answer

   • State Strassen's divide into 7 multiplications
   • Write recurrence T(n) = 7T(n/2) + O(n^2)
   • Apply Master theorem / recursion tree
   • Derive complexity O(n^{log_2 7}) ~ O(n^{2.81})
   • Mention improvement over naive O(n^3)
3. 7 Marks
   aCompute the optimal solution for knapsack problem using greedy method $N=3$, $M=20$, $(p_1, p_2, p_3) = (25, 24, 15)$, $(w_1, w_2, w_3) = (18, 15, 10)$
   How to answer

   • Compute profit/weight ratios for 3 objects
   • Sort by ratio descending for greedy fractional knapsack
   • Fill capacity M=20 in order, take fractions if needed
   • Compute total profit and optimal solution vector
   • State selection and maximum profit
4. 7 Marks
   bConstruct minimum cost spanning tree using:

   1. i)Prim's algorithm
   2. ii)Kruskal algorithm

   

   How to answer

   • List all edges with weights from given graph
   • Apply Prim's algorithm step-by-step from starting vertex
   • Apply Kruskal's algorithm sorting edges and avoiding cycles
   • Draw resulting minimum spanning trees
   • Compute total minimum cost
5. 7 Marks
   aSolve the solution for 0/1 knapsack problem using dynamic programming $N=3$, $m=6$ profits $(p_1, p_2, p_3) = (1, 2, 5)$ weights $(w_1, w_2, w_3) = (2, 3, 4)$.
   How to answer

   • Define 0/1 knapsack DP recurrence f(i,y)
   • Build DP table for N=3, m=6 with given p,w
   • Fill optimal profit values row by row
   • Traceback to find selected items
   • State maximum profit and solution vector
6. 7 Marks
   bWhat is a Graph, a Multistage graph? What is the application of a multistage graph?
   How to answer

   • Define graph, vertices, edges
   • Define multistage graph and stage partition property
   • Give example structure of multistage graph
   • List applications like resource allocation, shortest path
   • Explain multistage forward/backward approach use
7. 7 Marks
   aWrite an algorithm for Hamiltonian cycle with an example.
   How to answer

   • Define Hamiltonian cycle problem
   • State backtracking algorithm steps / pseudocode
   • Explain next-vertex and promising function
   • Illustrate with small example graph
   • Give time complexity
8. 7 Marks
   bWhat an algorithm for graph coloring and solve the following graph?

   

   How to answer

   • State m-colorability / graph coloring algorithm steps
   • Model map regions 1-5 as adjacency graph
   • Apply backtracking to assign colors
   • Show coloring solution and chromatic number
   • Conclude minimum colors needed
9. 7 Marks
   aExplain the method of reduction to solve traveling sales person problem using branch and bound.
   How to answer

   • Define TSP and branch and bound principle
   • Explain cost matrix reduction (row/column)
   • Show bound calculation and branching
   • Describe state space tree search for optimal tour
   • Mention reduction method steps
10. 7 Marks
    bSketch the state space tree degenerated by 4-queens problem.
    How to answer

    • Define 4-queens and constraints
    • Show root and level-wise placement
    • Draw pruned state space tree with promising nodes
    • Indicate solution nodes / dead ends
    • State number of solutions
11. 7 Marks
    aDistinguish NP- hard and NP-complete problems.
    How to answer

    • Define NP-hard with reduction from NP problems
    • Define NP-complete as NP + NP-hard
    • Compare on membership in NP, solvability, examples
    • Give examples: SAT, TSP, clique
    • Present differences in table
12. 7 Marks
    bWhat is a data stream algorithm? How are algorithms used in streaming services? Explain with an example.
    How to answer

    • Define data stream algorithm and constraints
    • Explain single-pass, sublinear memory processing
    • Describe use in streaming services with example
    • Give example like frequency counting / recommendation
    • Mention challenges and performance
13. 7 Marks
    aHow do you prove the Correctness proof of Greedy algorithm? Explain.
    How to answer

    • State greedy choice and optimal substructure properties
    • Explain exchange argument / staying ahead proof
    • Outline induction steps for correctness
    • Give example like MST or knapsack
    • Conclude conditions for greedy optimality
14. 7 Marks
    bFor the following matrix, Describe Strassen's matrix multiplication $$\begin{bmatrix} 4 & 5 \\ 5 & 9 \end{bmatrix} \begin{bmatrix} 2 & 10 \\ 1 & 6 \end{bmatrix}$$
    How to answer

    • Partition matrices into 2x2 blocks
    • Compute Strassen's 7 products M1-M7
    • Combine to get result blocks C11,C12,C21,C22
    • Show arithmetic for given numbers
    • State final product matrix
15. 14 Marks
    Write short notes on any two:

    1. a)Logic Optimization
    2. b)Optimal merge patterns
    3. c)If $f(n)=5n^2 + 6n + 4$, then prove that f(n) is $O(n^2)$
    4. d)Parallel Algorithm
    How to answer

    • Select any two topics from a-d
    • Give definition and key concepts for each
    • Explain algorithm/steps or proof as applicable
    • Add example or diagram where relevant
    • Conclude with applications