AL-402 Analysis and Design of Algorithm - Jun 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
   aExplain the various criteria used for analyzing algorithm.
   How to answer

   • Define time complexity, space complexity and other criteria
   • Explain correctness, optimality, readability and robustness
   • Discuss a priori vs a posteriori analysis with example
2. 7 Marks
   bWhat is merge sort? Explain merge sort algorithm for the list: 65, 47, 24, 83, 91, 14, 53, 12
   How to answer

   • Define merge sort and divide-and-conquer principle
   • Write merge sort and merge procedure steps / pseudocode
   • Apply step-by-step to list 65, 47, 24, 83, 91, 14, 53, 12
   • State time complexity O(n log n)
3. 7 Marks
   aWrite the algorithm for Stassen's matrix multiplication.
   How to answer

   • State Strassen's divide-and-conquer idea for matrix multiplication
   • Give 7 intermediate products M1-M7 formulas
   • Give steps to compute result submatrices C11, C12, C21, C22
   • Mention complexity O(n^2.81)
4. 7 Marks
   bDefine Kruskal's algorithm and also write down the steps for the Kruskal's algorithm in detail.
   How to answer

   • Define Kruskal's algorithm for minimum spanning tree
   • Steps: sort edges, initialize disjoint sets, select min edge avoiding cycle
   • Explain union-find operations
   • Give complexity O(E log E)
5. 7 Marks
   aExplain how job sequencing with deadline can be solved using deadlines.
   How to answer

   • Define job sequencing with deadlines, profit objective
   • Explain greedy sorting by profit and slot allocation
   • Describe feasibility check using deadlines
   • Illustrate with example schedule
6. 7 Marks
   bExplain minimum spanning tree using Prim's algorithm for the given graph below.

   

   How to answer

   • State Prim's algorithm principle starting from arbitrary vertex
   • Show iterative selection of minimum fringe edge step-by-step on given graph
   • Construct MST and compute total cost
   • State complexity O(V^2) / O(E log V)
7. 14 Marks
   Explain Floyd-Warshall algorithm with suitable example.
   How to answer

   • Explain all-pairs shortest path dynamic programming recurrence
   • Give Floyd-Warshall pseudocode with k,i,j loops
   • Work out suitable example with distance matrix iterations
   • State complexity O(n^3)
8. 7 Marks
   aFind optimal solution for 0/1 Knapsack problem $(w_1, w_2, w_3, w_4) = (10, 10, 12, 18); (P_1, P_2, P_3, P_4) = (2, 4, 6, 0)$ and $M = 15$.
   How to answer

   • List weights (10,10,12,18), profits (2,4,6,0), capacity M=15
   • Evaluate feasible 0/1 subsets / DP table
   • Select optimal feasible set maximizing profit
   • State optimal profit and selected items
9. 7 Marks
   bExplain in detail 8-Queens problem.
   How to answer

   • State 8-Queens constraints: row, column, diagonal attacks
   • Explain backtracking state-space tree formulation
   • Describe placement and backtrack steps with example
   • Mention solution existence and complexity
10. 7 Marks
    aWrite about different types of bounding functions with example.
    How to answer

    • Define bounding function in branch and bound
    • Explain lower/upper bound for minimization/maximization
    • Give examples e.g. knapsack, TSP bounding
    • Compare different types
11. 7 Marks
    bFind the optimal solution using least cost branch and bound with $n = 4, m = 15$. $(w_1, w_2, w_3, w_4)=(3,5,6,9); (P_1,P_2,P_3,P_4)=(15,15,17,23)$
    How to answer

    • Compute profit/weight ratios and initial bound
    • Expand least-cost branch and bound tree for n=4, m=15
    • Prune infeasible / bounded nodes
    • Report optimal 0/1 selection and max profit
12. 14 Marks
    Discuss in detail P, NP, NP complete and NP Hard problems with examples.
    How to answer

    • Define classes P, NP, NP-complete, NP-hard
    • Explain polynomial verification and reduction concept
    • Give examples e.g. sorting in P, SAT, TSP, clique
    • Show relationship diagram between classes
13. 14 Marks
    Write short notes on any three of the following.

    1. a)Binary search trees
    2. b)Huffman coding
    3. c)Multistage graph
    4. d)Hamiltonian cycle
    5. e)Quick sort.
    How to answer

    • Select any three topics from a-e
    • For each: definition, working principle / algorithm steps
    • Give example / diagram / complexity where applicable
    • Conclude with applications