CS-402 Analysis 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
   aTrace the quick sort algorithm to sort the list C, O, L, L, E, G, E in alphabetical order.
   How to answer

   • Choose pivot element from the list
   • Partition elements into smaller and larger subsets
   • Recursively apply quicksort to partitions
   • Combine results to get sorted sequence: C, E, E, G, L, L, O
2. 7 Marks
   bDiscuss Strassen's matrix multiplication and derive its time complexity.
   How to answer

   • Explain Strassen's divide-and-conquer approach using 7 multiplications instead of 8
   • Provide recurrence relation: T(n) = 7T(n/2) + cn²
   • Apply Master theorem to derive T(n) = O(n^log₇2) ≈ O(n^2.81)
   • Compare with standard multiplication O(n³)
3. 7 Marks
   aDesign merge sort algorithm and discuss its best-case, average-case and worst-case Efficiency.
   How to answer

   • Present merge sort pseudocode with divide-and-conquer strategy
   • Best-case: O(n log n) when already sorted
   • Average-case: O(n log n) for random inputs
   • Worst-case: O(n log n) for reverse sorted or random inputs
   • Space complexity: O(n) auxiliary space needed
4. 7 Marks
   bHow to solve the Knapsack problem with greedy method? Explain.
   How to answer

   • Calculate profit-to-weight ratio for each item
   • Sort items in decreasing order of ratio
   • Select items greedily until knapsack capacity is full
   • Note: Greedy method does not guarantee optimal solution for 0/1 knapsack
   • Suitable for fractional knapsack problem
5. 7 Marks
   aWrite an algorithm for single source shortest path and explain with an example.
   How to answer

   • Maintain distance array initialized with infinity except source (0)
   • Use priority queue or minimum-distance selection strategy
   • Update distances of adjacent vertices iteratively
   • Mark processed vertices to avoid revisiting
   • Provide traced example with weighted graph showing steps
6. 7 Marks
   bDiscuss briefly about the minimum spanning tree.
   How to answer

   • Definition: tree with minimum total edge weight connecting all vertices
   • Properties: acyclic, connected, contains n-1 edges for n vertices
   • Algorithms: Kruskal's and Prim's methods
   • Applications in network design, clustering, and optimization
   • Uniqueness: MST may not be unique if edge weights are equal
7. 7 Marks
   aWhat do you mean by forward and backward approach of problem solving in Dynamic Programming?
   How to answer

   • Forward approach (bottom-up): solve smaller subproblems first, build solutions upward
   • Backward approach (top-down): solve from target, recursively solve subproblems
   • Forward uses tabulation, backward uses memoization
   • Forward avoids redundant computation by iterative calculation
   • Backward more intuitive but may have overhead of recursion
8. 7 Marks
   bHow the reliability of a system is determined using dynamic programming? Discuss.
   How to answer

   • Model system with stages and redundant components at each stage
   • Assign reliability probabilities to components
   • Use DP to find maximum reliability by selecting component combinations
   • Recurrence: R(i,j) = max reliability using j components up to stage i
   • Consider cost constraints and stage-wise decision making
9. 7 Marks
   aFind an optimal solution for following 0/1 Knapsack problem using dynamic programming: Number of objects $n = 4$, Knapsack Capacity $M = 5$, Weights $(W_1, W_2, W_3, W_4) = (2, 3, 4, 5)$ and Profits $(P_1, P_2, P_3, P_4) = (3, 4, 5, 6)$.
   How to answer

   • Build DP table with rows for each object and columns for capacity 0 to 5
   • Fill table using recurrence: V[i,w] = max(V[i-1,w], P[i] + V[i-1,w-W[i]])
   • Backtrack from V[4,5] to find selected items
   • Expected optimal: select objects 1 and 2 for total profit 7 and weight 5
   • Present DP table and trace of selected items
10. 7 Marks
    bExplain the 8 queen's problem and apply the backtracking to solve the 8 queen's problem.
    How to answer

    • Problem: place 8 queens on 8×8 chessboard with no attacks
    • Constraints: no two queens in same row, column, or diagonal
    • Backtracking approach: place queens column by column
    • For each column, try each row and check if placement is safe
    • If unsafe, backtrack and try next row; if all rows fail, return to previous column
    • Continue until all 8 queens are placed or prove no solution exists
11. 14 Marks
    Write the control abstraction for LC-Search. Explain how Traveling Salesperson problem is solved using LCBB.
    How to answer

    • Control abstraction: use priority queue to explore nodes with minimum cost bound
    • LCBB = Least Cost with Branch and Bound strategy
    • For TSP: compute lower bound for each partial tour using reduced cost matrix
    • Expand node with least lower bound; prune branches exceeding best solution
    • Continue until all nodes explored or upper bound reached; report best tour found
12. 7 Marks
    aDiscuss the differences between BFS and DFS.
    How to answer

    • BFS uses queue, explores level by level; DFS uses stack, explores deeply first
    • BFS: finds shortest path in unweighted graphs; DFS: detects cycles and back edges
    • BFS: space O(w) for width; DFS: space O(h) for height
    • BFS: complete and optimal; DFS: not always complete without cycle detection
    • Comparison table of traversal order, data structure, time/space complexity
13. 7 Marks
    bWhat are 2-3 trees used for? Why are 2-3 trees better than BST trees? Write the limitations of 2-3 tree in CSE.
    How to answer

    • 2-3 trees used for maintaining sorted data with guaranteed balance
    • Better than BST: always remain balanced ensuring O(log n) search/insert/delete
    • BST can degenerate to O(n) in worst case with skewed insertions
    • Limitations: more complex implementation, higher constant factors, overhead for maintaining balance
    • Limitations in practice: slower than some other balanced trees due to node structure
14. 14 Marks
    Discuss briefly any two of the following: a) Heap sort b) Dynamic Programming c) Height balanced tree d) Parallel algorithm
    How to answer

    • Brief explanation of any two topics selected from the four options
    • For each topic: definition, key features, complexity analysis or usage
    • Concise presentation of core concepts without deep derivation
    • Examples where applicable for clarity