AL-402 Analysis and Design of Algorithm - Nov 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
   aDefine time complexity. Describe different notations used to represent time complexity.
   How to answer

   • Define time complexity as function of input size
   • Explain Big-O, Omega, Theta (and little-o) notations
   • Give mathematical definitions and examples
   • Explain use in worst/best/average case analysis
2. 7 Marks
   bDiscuss Strassen's matrix multiplication as well as classical $O(n^2)$ one. Determine when Strassen's method outperforms the classical one.
   How to answer

   • Describe classical matrix multiplication O(n^3) method
   • Explain Strassen's 7-multiplication divide-and-conquer steps
   • Give recurrence and complexity O(n^log2 7)
   • Compare crossover point where Strassen outperforms classical
3. 7 Marks
   aExplain partition exchange sort algorithm and trace this algorithm for $n = 8$ elements: 24, 12, 35, 23, 45, 34, 20, 48.
   How to answer

   • Explain quick sort / partition exchange sort partition logic
   • Give algorithm pseudocode and pivot steps
   • Trace partitions on given 8 elements
   • Show final sorted order and complexity
4. 7 Marks
   bState the Job - Sequencing with deadlines problem. Find an optimal sequence to the $n = 5$ Jobs where profits $(P_1, P_2, P_3, P_4, P_5) = (20, 15, 10, 5, 1)$ and deadlines $(d_1, d_2, d_3, d_4, d_5)=(2, 2, 1, 3, 3)$.
   How to answer

   • State job sequencing with deadlines formulation
   • Sort jobs by profit and apply greedy deadline constraint
   • Construct feasible optimal sequence
   • Compute maximum profit
5. 7 Marks
   aA thief enters a house for robbing. Thief can carry a maximum weight of 6kg into his bag. There are 3 items in the house with weights $(w_1, w_2, w_3) = (2, 3, 4)$ and profits $(p_1, p_2, p_3) = (1, 2, 5)$ what items should thief can take will get the maximum profit? He either takes or leaves the item.
   How to answer

   • Identify as 0/1 knapsack with capacity 6kg
   • Compute profit/weight or DP table for 3 items
   • Select take-or-leave combination with max profit
   • State items taken and maximum profit
6. 7 Marks
   bExplain prim's and Kruskal's algorithm shown in figure with the following example.

   

   How to answer

   • Explain Prim's growing-tree and Kruskal's sorted-edge rules
   • Apply both step-by-step on given 7-node weighted graph
   • Show MST edges selected at each step
   • Compare total cost and complexity
7. 7 Marks
   aSolve the following instance of 0/1 Knapsack problem using Dynamic programming. $n = 3$; $(W_1, W_2, W_3) = (3, 5, 7)$; $(P_1, P_2, P_3) = (3, 7, 12)$; $M = 4$.
   How to answer

   • Formulate 0/1 knapsack DP recurrence
   • Build DP table for n=3, M=4
   • Trace back optimal selection
   • State max profit and items selected
8. 7 Marks
   bDesign 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 with cost constraint $105
   • Use DP for multistage reliability optimization
   • Evaluate device counts for D1, D2, D3
   • Give max reliability design
9. 7 Marks
   aDiscuss about Multistage graph problem. Also give a suitable algorithm and find its computing time.
   How to answer

   • Define multistage graph and stages
   • Give forward/backward DP algorithm
   • Analyze computing time O(V+E)
   • Illustrate with example
10. 7 Marks
    bWrite an algorithm to determine the Hamiltonian cycle in a given graph using backtracking.
    How to answer

    • Explain backtracking state-space formulation
    • Give Hamiltonian cycle pseudocode with promising function
    • Explain NextValue and backtrack steps
    • State time complexity
11. 7 Marks
    aSolve the following instance of travelling sales person problem using Least Cost Branch Bound.

    

    How to answer

    • Formulate TSP as LC branch and bound
    • Compute reduced cost bounds for nodes
    • Expand state space tree to find least cost tour
    • Give optimal tour and cost
12. 7 Marks
    bConstruct state space tree for solving four queen's problem using backtracking.
    How to answer

    • Explain 4-queens backtracking constraints
    • Draw state space tree with pruning
    • Show feasible placements
    • Give solutions
13. 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 classes
    • Give examples of problems in each class
    • Explain reducibility and relation diagram
    • State P vs NP relationship
14. 7 Marks
    bShow the inorder, preorder and postorder for the following tree

    

    How to answer

    • Parse given binary tree structure
    • List preorder traversal (root-left-right)
    • List inorder traversal (left-root-right)
    • List postorder traversal (left-right-root)
15. 14 Marks
    Write short notes on any two of the following

    1. a)Data Transfer Optimization and Logic Optimization
    2. b)Differentiate between prim's algorithm and Kruskal's algorithm
    3. c)Parallel algorithms
    4. d)Approximation Algorithms
    How to answer

    • Select any two topics from a-d
    • Give definition and key concepts for each
    • Explain algorithm/steps with example
    • Mention applications/complexity