Skip to content
EndsemNov 20252019 patternBE Comp

Design & Analysis of Algorithms (DAA) SPPU Endsem Question Paper Nov 2025

All 8 questions from this SPPU endsem paper, as printed. Read them here or open the PDF.

Open the PDFMost repeated DAA questions
Subject code
410241
Pattern
2019 pattern
Exam
Endsem
Session
Nov 2025
Max. marks
70
Time
2½ Hours
Semester
VII
Paper code
[6584]-91

Printed for: B.E. (Computer Engineering)

Instructions to the candidates

  1. Attempt Q.1 or Q.2, Q.3 or Q.4, Q.5 or Q.6, Q.7 or Q.8
  2. Neat diagrams must be drawn whenever necessary.
  3. Assume suitable data, if necessary.
  4. Figures to the right indicate full marks.

Questions

  1. Q1

    1. a)

      Compare greedy algorithmic strategy and dynamic programming strategy.

      [6]
    2. b)

      This part has equations that don’t show as text. Open the PDF to read it.

      [8]
    3. c)

      Comment on the statement “Greedy method always provides the optimal solution”.

      [3]

  2. Q2

    1. a)

      Write a control abstraction for dynamic programming strategy. Comment on the time complexity of this abstraction?

      Also asked:May 2024

      [7]
    2. b)

      Find the binomial coefficients of (x+y) 5 , using dynamic programming approach. 2

      [10]

  3. Q3

    1. a)

      Consider the set A of five numbers {5,10,15,20,25}. We wish to find the subset of A such that sum of the numbers in this subset is equal to 30. Solve this problem to find the first solution using backtracking approach. Show space tree being created.

      Also asked:May 2024

      [10]
    2. b)

      Write a control abstraction for branch and bound strategy, Enlist few applications of branch and bound method.

      [8]

  4. Q4

    1. a)

      This part has equations that don’t show as text. Open the PDF to read it.

      [10]
    2. b)

      Write an algorithm for graph colouring problem using backtracking method. Let the graph consists of n nodes and that there are m-number of availble colours. What is the time complexity of this algorithm?

      [8]

  5. Q5

    1. a)

      Prove that amortized cost per operation in k-bit binary counter is O(1).

      [5]
    2. b)

      What are intractable problems? Does traveling salesperson Problem belong to this class of problems? Justify your answer.

      [6]
    3. c)

      Briefly explain any two methods of amortized analysis.

      Also asked:May 2025 ·May 2024 ·Nov 2023

      [6]

  6. Q6

    1. a)

      Explain in brief amortized analysis. Consider stack as an example and single push, single pop and multiple pop operations. Give the amortized costs for these stack operations.

      [9]
    2. b)

      Does randomized algorithm for quick sort, improves the average case time complexity? Discuss.

      Also asked:May 2025

      [4]
    3. c)

      Comment on the statement “The problem of Searching an ordered list or searching an unordered list belongs to the class of tractable problems”. 3

      [4]

  7. Q7

    1. a)

      Let the hash code for the text be “4133124” and that for the pattern matching text be “124”. Use modulo arithmetic with the prime number 13 and apply Rabin-Karp string matching algorithm for this case. Show the stepwise process of matching the pattern. What is the time complexity of this algorithm?

      [10]
    2. b)

      Compare and contrast row-wise and block-wise approaches in multithreaded matrix multiplication with respect to: division of work, communication overhead and cache efficiency.

      [8]

  8. Q8

    1. a)

      Consider the text T and the pattern text P. Write a naïve string-matching algorithm. Show the stepwise process of working of this algorithm if T = “KITCHEN” and P = “HEN”.

      [10]
    2. b)

      Write a distributed algorithm to find the minimum spanning tree. 

      [8]