CY-502 Design and Analysis of Algorithm - Dec 2025 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 an algorithm. Explain time and space complexity and the concept of time-space tradeoff.
   How to answer

   • Define algorithm: finite, definite, effective steps
   • Define time complexity and space complexity with examples
   • Explain time-space tradeoff concept with example
2. 7 Marks
   bExplain asymptotic notations $O$, $\Omega$ and $\Theta$ with suitable examples.
   How to answer

   • Define Big-O, Omega, Theta formally
   • Give mathematical definitions with inequalities
   • Provide suitable example for each notation
3. 7 Marks
   aExplain recurrence relations and methods to solve them.
   How to answer

   • Define recurrence relation in algorithm analysis
   • Explain substitution method
   • Explain recursion-tree method and Master method
4. 7 Marks
   bSolve the recurrence, $T(n)=2T(n/2) + n$ using Master's methods.
   How to answer

   • Identify a=2, b=2, f(n)=n for Master theorem
   • Compute $n^{\log_b a}$ and compare with f(n)
   • Apply Case 2 to get $T(n)=\Theta(n \log n)$
5. 7 Marks
   aExplain the divide and conquer technique with reference to merge sort.
   How to answer

   • Explain divide, conquer, combine phases
   • Explain merge sort procedure with example
   • Give recurrence and $O(n \log n)$ complexity
6. 7 Marks
   bApply binary search to find 25 in the sorted array, $[5, 10, 15, 20, 25, 30, 35]$. Show the steps.
   How to answer

   • Start with low=0, high=6, find mid
   • Compare mid element with 25 and adjust bounds
   • Show steps until 25 found at index 4
7. 7 Marks
   aExplain the greedy method. Discuss its strategy and characteristics.
   How to answer

   • Define greedy method and greedy choice
   • Explain strategy: local optimum, feasibility, irrevocable
   • List characteristics: greedy-choice property, optimal substructure
8. 7 Marks
   bConstruct a minimum spanning tree using Kruskal's algorithm for the given graph as shown in FIGURE (A) as mentioned below.

   

   How to answer

   • List all edges of FIGURE (A) sorted by weight
   • Iteratively add least-weight edge avoiding cycle
   • Obtain MST and compute total minimum cost
9. 7 Marks
   aExplain dynamic programming and its characteristics.
   How to answer

   • Define dynamic programming and principle of optimality
   • Explain overlapping subproblems and memoization
   • List characteristics with example
10. 7 Marks
    bSolve the 0/1 knapsack problem for weights $\{2, 3, 4\}$, values $\{1, 2, 5\}$ and capacity $= 5$.
    How to answer

    • Build DP table for weights {2,3,4}, values {1,2,5}, capacity 5
    • Evaluate optimal value by considering include/exclude
    • Trace back optimal item set and maximum profit
11. 7 Marks
    aExplain the concept of backtracking with reference to the 8-queens problem.
    How to answer

    • Define backtracking and state-space tree
    • Explain constraints for 8-queens: row, column, diagonal
    • Describe recursive placement and backtrack steps
12. 7 Marks
    bApply the Branch and Bound algorithm to solve the travelling salesperson problem for the given graph as shown in FIGURE (B)

    

    How to answer

    • Formulate TSP cost matrix from FIGURE (B)
    • Apply Branch and Bound: compute bounds and expand nodes
    • Identify minimum-cost tour and its cost
13. 7 Marks
    aExplain NP-hard and NP-complete problems with suitable examples.
    How to answer

    • Define NP, NP-hard with reducibility concept
    • Define NP-complete with NP + NP-hard
    • Give examples e.g. SAT, TSP, Vertex Cover
14. 7 Marks
    bWhat are approximation algorithms? Explain their need and applications.
    How to answer

    • Define approximation algorithms and ratio bound
    • Explain need: NP-hard problems, large inputs
    • Give applications e.g. TSP, Vertex Cover, scheduling
15. 7 Marks
    aDiscuss advanced tree and graph algorithms. Explain the importance of shortest path algorithms.
    How to answer

    • Discuss advanced tree/graph models
    • Explain Dijkstra, Bellman-Ford, Floyd-Warshall
    • Highlight importance of shortest path in networks
16. 7 Marks
    bWrite short notes on data stream algorithms and parallel algorithms.
    How to answer

    • Define data stream algorithms: single-pass, sublinear space
    • Define parallel algorithms: speedup, PRAM
    • Give applications and examples for both