AL-402 Analysis and Design of Algorithm - Jun 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
   aDescribe the performance analysis of an algorithm in detail.
   How to answer

   • Define time and space complexity, a priori vs a posteriori analysis
   • Explain asymptotic notations O, Omega, Theta with definitions
   • Discuss best, average, worst case and performance measurement steps
   • Give example of counting steps / frequency count
2. 7 Marks
   bConsider the following recurrence $T(n)=3T(n/3) + n$ obtain asymptotic bound using substitution method.
   How to answer

   • Guess asymptotic bound e.g. $T(n)=O(n^{\log_3 3})$
   • Assume inductive hypothesis $T(k) \le c k^{\log}$ for $k<n$
   • Substitute into $T(n)=3T(n/3)+n$ and solve for c
   • Conclude Theta bound and verify base case
3. 7 Marks
   aWrite Divide - And - Conquer recursive Quick sort algorithm and analyze the algorithm for average time complexity.
   How to answer

   • Write Divide-and-Conquer Quick sort partition + recursive calls
   • Set up recurrence for average case
   • Solve to get $O(n \log n)$ average complexity
   • Discuss pivot choice and partitioning cost
4. 7 Marks
   bApply the Greedy method to solve Knapsack problem for given instance. Where $n = 3$, $m = 20$, $(p_1, p_2, p_3) = (25, 24, 15)$ and weight $(w_1, w_2, w_3) = (18, 15, 10)$
   How to answer

   • Compute profit/weight ratios for $n=3$ items
   • Sort by ratio and take fractionally up to $m=20$
   • Compute total profit $\sum p_i x_i$
   • Show greedy selection steps
5. 7 Marks
   aWrite Kruskal's Algorithm. Generate the MCST for the graph given in Figure 1 by applying Kruskal's algorithm.

   

   How to answer

   • Write Kruskal's algorithm steps with sort + union-find
   • Sort edges of Figure 1 by weight
   • Select edges avoiding cycle step by step
   • Draw final MCST and compute total cost
6. 7 Marks
   bObtain a set of optimal Huffman codes for the seven messages (M1, ... , M7) with relative frequencies $(q1, ... , q7) = (4, 5, 7, 8, 10, 22, 15)$. Draw the decode tree for this set of codes.
   How to answer

   • Sort frequencies (4,5,7,8,10,22,15) ascending
   • Repeatedly merge two smallest to build Huffman tree
   • Assign 0/1 codes and list optimal codes
   • Draw decode tree with M1..M7 leaves
7. 7 Marks
   aSolve the following 0/1 Knapsack problem using dynamic programming $P = (11, 21, 31, 33)$, $W = (2, 12, 23, 15)$, $C = 42$, $n = 4$.
   How to answer

   • Formulate 0/1 knapsack DP table for P=(11,21,31,33), W=(2,12,23,15), C=42
   • Fill DP recurrence $V[i][w]=max$
   • Trace back optimal subset
   • State max profit and selected items
8. 7 Marks
   bExplain Floyd Warshall algorithm problem with the graph given in figure.

   

   How to answer

   • State Floyd-Warshall all-pairs shortest path recurrence
   • Initialize distance matrix from given graph
   • Iterate k = A..F updating distances
   • Show final shortest distances
9. 7 Marks
   aWhat is multistage graph problem? Discuss its solution based on dynamic programming approach. Also give a suitable algorithm and find its computing time?
   How to answer

   • Define multistage graph and stages
   • Give forward/backward DP recurrence for min cost
   • Write algorithm and analyze $O(|V|+|E|)$ time
   • Illustrate with example
10. 7 Marks
    bFind a solution to the 8-Queens problem using backtracking strategy. Draw the solution space using necessary bounding function.
    How to answer

    • Explain backtracking with bounding function and state space tree
    • Place queens row by row checking column/diagonal
    • Show one 8-queens solution vector
    • Draw pruned solution space tree
11. 7 Marks
    a

    Solve the traveling salesperson problem using branch and bound technique.

    	A	B	C
    A	0	3	4
    B	6	0	4
    C	3	5	0

    How to answer

    • Write cost matrix for A,B,C
    • Expand branch-and-bound state space with lower bounds
    • Prune and select minimum cost tour
    • State optimal TSP tour and cost
12. 7 Marks
    bWhat is Backtracking? Discuss any one problem solved by backtracking. Also give its advantages and disadvantages.
    How to answer

    • Define backtracking as DFS with backtrack on dead end
    • Explain one example e.g. N-Queens / sum of subsets / graph coloring
    • List advantages: pruning, memory efficient
    • List disadvantages: exponential worst case
13. 7 Marks
    aCompare and contrast NP-Hard and NP-Complete classes.
    How to answer

    • Define NP-Hard and NP-Complete with reducibility
    • Compare on definition, relation, solvability
    • Give examples: SAT, TSP, clique
    • Conclude NP-Complete subset of NP-Hard
14. 7 Marks
    bCreate a B-tree for the following list of elements $L = \{86, 50, 40, 3, 94, 10, 70, 90, 110, 113, 116\}$ given minimization factor $t = 3$, minimum degree $= 2$ and maximum degree $= 5$.
    How to answer

    • State B-tree properties for t=3, min degree 2, max degree 5
    • Insert keys {86,50,40,3,94,10,70,90,110,113,116} stepwise with splits
    • Show intermediate nodes after each split
    • Draw final B-tree
15. 14 Marks
    Write short notes on any two of the following:

    1. a)Reliability design
    2. b)Correctness proof of Greedy algorithms
    3. c)Design and complexity of Parallel Algorithms
    4. d)Graph coloring problem
    How to answer

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