CY-502 Design And Analysis of Algorithms - Jun 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 algorithm. Explain different characteristics of algorithm with suitable example.
   How to answer

   • Definition of algorithm as finite step-by-step procedure
   • List characteristics: input, output, definiteness, finiteness, effectiveness
   • Explain each characteristic briefly
   • Give suitable example e.g. sorting / Euclid's GCD with steps
2. 7 Marks
   bExplain Strassens Matrix multiplication and also find the time complexity.
   How to answer

   • Outline Strassen's divide-and-conquer matrix multiplication with 7 multiplications
   • Give formulae for M1-M7 and result submatrices
   • Recurrence T(n)=7T(n/2)+O(n^2)
   • Solve to O(n^log2 7) ~ O(n^2.81) time complexity
3. 14 Marks
   Define spanning tree? Construct a minimal spanning tree for the given graph.

   

   How to answer

   • Define spanning tree and minimal spanning tree
   • Apply Kruskal's or Prim's algorithm stepwise on given weighted graph
   • Show selected edges in order avoiding cycles
   • Draw final MST and give total minimum cost
4. 14 Marks
   Explain multistage graph for the following graph.

   

   How to answer

   • Define multistage graph and stages
   • Explain forward/backward dynamic programming recurrence for shortest path
   • Apply to given 4-stage graph from source 0 to sink 7
   • Find minimum cost path and optimal route
5. 7 Marks
   aExplain 8-queen problem with state space tree.
   How to answer

   • State 8-queen placement constraints
   • Explain backtracking and state space tree concept
   • Show partial tree with promising and non-promising nodes
   • Mention solution existence and example solution
6. 7 Marks
   bExplain graph coloring problem with suitable example.
   How to answer

   • Define graph coloring and chromatic number
   • Explain m-colorability backtracking approach
   • Illustrate with small graph example and coloring steps
   • Mention applications
7. 7 Marks
   aExplain NP Hard and NP Complete Problems with examples.
   How to answer

   • Define P, NP, NP-Hard and NP-Complete classes
   • Explain reducibility and polynomial-time verification
   • Give examples e.g. SAT, TSP, Knapsack, Graph coloring
   • Show relationship diagram between classes
8. 7 Marks
   bExplain Algorithm for Data stream.
   How to answer

   • Define data stream model and its constraints
   • Explain single-pass, limited memory processing
   • Describe sampling / sketching / sliding window algorithm
   • Give application example
9. 7 Marks
   aExplain single source shortest path problem with suitable example.
   How to answer

   • Define single source shortest path problem
   • Explain Dijkstra's / Bellman-Ford steps
   • Trace on suitable weighted graph example
   • Give time complexity and limitations
10. 7 Marks
    bExplain different uses of Lower bound theory.
    How to answer

    • Define lower bound theory
    • Explain methods: comparison trees, oracle, state space
    • List uses: proving optimality, comparing algorithms
    • Give example e.g. sorting Omega(n log n)
11. 7 Marks
    aExplain merge sort for the following elements 20, 30, 15, 11, 35, 19, 12, 11, 55.
    How to answer

    • Explain merge sort divide-and-conquer steps
    • Recursively split list 20,30,15,11,35,19,12,11,55
    • Show merging of sorted sublists stepwise
    • Give final sorted order and O(n log n) complexity
12. 7 Marks
    bExplain data transfer optimization with example.
    How to answer

    • Define data transfer optimization
    • Explain batching, compression, caching strategies
    • Illustrate with network / distributed example
    • Mention cost and time benefits
13. 14 Marks
    Write a short notes on the following:

    1. a)Time complexity
    2. b)graphs
    3. c)trees
    How to answer

    • Define time complexity with Big-O, Omega, Theta
    • Define graph: vertices, edges, types
    • Define tree: properties, binary tree, spanning tree
    • Give examples and applications for each