AL-402 Analysis and Design of Algorithm - 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
   aSolve the following recurrence relation $T(n) = 7T(n/2) + cn^{2}$.
   How to answer

   • State Master theorem / recursion tree method assumptions
   • Expand T(n)=7T(n/2)+c n^2 level by level
   • Compare n^{log2 7} vs n^2 to get Theta(n^{log2 7})
   • Write final asymptotic solution
2. 7 Marks
   bShow how quick sort sorts the following sequence of keys $65, 70, 75, 80, 85, 60, 55, 50, 45$ Solve the recurrence relation of quick sort using substitution method.
   How to answer

   • Choose pivot and show partition steps for given keys
   • Show recursive quick sort calls and intermediate arrays
   • Write quick sort worst/average recurrence
   • Solve recurrence by substitution method
3. 7 Marks
   aExplain merge sort algorithm and find the complexity of the algorithm.
   How to answer

   • Explain divide, conquer and merge steps of merge sort
   • Give pseudocode / algorithm
   • Derive recurrence T(n)=2T(n/2)+O(n)
   • Solve to O(n log n) time and O(n) space
4. 7 Marks
   bWrite an algorithm for single source shortest path and apply it for the following graph.

   

   How to answer

   • State single-source shortest path algorithm (Dijkstra)
   • Give pseudocode and initialization steps
   • Apply relaxation step by step on given graph
   • Report shortest distances / shortest path tree
5. 7 Marks
   aHow the Optimal Merge Pattern algorithm works? Explain with a suitable example.
   How to answer

   • Define optimal merge pattern objective
   • Explain greedy choice using smallest files / min-heap
   • Illustrate with suitable numeric example
   • Give time complexity analysis
6. 7 Marks
   bApply Kruskal's algorithm to find the minimum spanning tree of a graph with weighted edges.

   

   How to answer

   • State Kruskal's rule: sort edges and avoid cycles
   • Sort all weighted edges in increasing order
   • Select edges using union-find step by step
   • Obtain minimum spanning tree and its total cost
7. 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 DP forward/backward recurrence for cost
   • Write algorithm pseudocode
   • Analyze computing time O(n+e) / O(stages)
8. 7 Marks
   bCompute the optimal solution for knapsack problem using greedy method $N = 5, M = 10, (p_{1}, p_{2}, p_{3}, p_{4}, p_{5}) = (10, 15, 10, 12, 8), (w_{1}, w_{2}, w_{3}, w_{4}, w_{5}) = (3, 3, 2, 5, 1)$.
   How to answer

   • Compute profit/weight ratios for N=5 items
   • Sort by ratio for fractional knapsack greedy
   • Fill capacity M=10 step by step
   • Compute maximum profit and optimal solution vector
9. 7 Marks
   aDesign a three stage system with device types $D_{1}, D_{2}$ and $D_{3}$. The costs are $\$30, \$15$ and $\$20$ respectively. The Cost of the system is to be no more than $\$105$. The reliability of each device is $0.9, 0.8$ and $0.5$ respectively.
   How to answer

   • State reliability design / redundancy optimization model
   • Use costs $30,$15,$20 and reliabilities 0.9,0.8,0.5 with budget $105
   • Apply DP for three stages to allocate devices
   • Give optimal design and maximum reliability
10. 7 Marks
    bBriefly explain the Hamiltonian cycle using backtracking with a example.
    How to answer

    • Define Hamiltonian cycle problem
    • Explain backtracking state-space tree and pruning
    • Illustrate with example graph trace
    • Give algorithm and complexity
11. 14 Marks
    Solve the following instance of travelling sales person problem using Branch Bound. $$\begin{bmatrix} \infty & 20 & 30 & 10 & 11 \\ 15 & \infty & 16 & 4 & 2 \\ 3 & 5 & \infty & 2 & 4 \\ 19 & 6 & 18 & \infty & 3 \\ 16 & 4 & 7 & 16 & \infty \end{bmatrix}$$
    How to answer

    • Write given 5x5 cost matrix with infinities
    • Perform row and column reduction for root bound
    • Branch on edges and compute bounds for nodes
    • Trace least-cost tour and give optimal cost
12. 7 Marks
    aExplain the P, NP-Hard and NP-complete classes? Give the relation between them.
    How to answer

    • Define P, NP, NP-Hard, NP-Complete
    • Give example problems for each class
    • Explain reducibility and relation diagram
    • Discuss P vs NP significance
13. 7 Marks
    bExplain the purpose of design and complexity of parallel algorithms in detail.
    How to answer

    • Define parallel algorithm model
    • Explain purpose: speedup, efficiency, scalability
    • Discuss complexity measures: time, processors, cost
    • Give examples of design issues
14. 14 Marks
    Write short notes on any two of the following:

    1. a)Logic Optimization
    2. b)Optimal merge patterns
    3. c)Data Transfer Optimization
    4. d)8 queen's problem using backtracking
    How to answer

    • Select any two topics from four options
    • Give definition and key concepts for each
    • Mention algorithm / steps / applications
    • Conclude with example or use-case