Skip to content
EndsemMay 20252019 patternBE Comp

Design & Analysis of Algorithms (DAA) SPPU Endsem Question Paper May 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
May 2025
Max. marks
70
Time
2½ Hours
Semester
VII
Paper code
[6404]-81

Printed for: B.E.(Computer Engineering)

Instructions to the candidates

  1. Answer 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 wherever necessary.
  3. Assume suitable data, if necessary.
  4. Figures to the right indicate full marks.

Questions

  1. Q1

    1. a)

      Give a mathematical formulation for: i) Fractional Knapsack problem ii) 0/1 Knapsack problem.

      [8]
    2. b)

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

      [9]

  2. Q2

    1. a)

      With respect to dynamic programming, what is the principle of optimality? Give a mathematical representation for the same.

      [7]
    2. b)

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

      [10]

  3. Q3

    1. a)

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

      [10]
    2. b)

      Prove that the full state space tree of finding sum of subset of n elements using backtracking will have (excluding the leaf nodes)2 n -1 nodes.

      [4]
    3. c)

      What are the major drawbacks of branch and bound method?

      Also asked:Nov 2024

      [4]

  4. Q4

    1. a)

      State the sum of subsets problem. Write an algorithm to solve this problem using backtracking method. Comment on the time complexity of this algorithm.

      [8]
    2. b)

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

      [10]

  5. Q5

    1. a)

      Give an amortized analysis of a k bit binary counter using aggregate method.

      [6]
    2. b)

      What are tractable and non-tractable problems? Give examples.

      [7]
    3. c)

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

      Also asked:Nov 2025

      [4]

  6. Q6

    1. a)

      Explain with the help of example the methods of amortized analysis.

      Also asked:Nov 2025 ·May 2024 ·Nov 2023

      [6]
    2. b)

      What is an approximation algorithm? How does performance ratios useful in approximation algorithms?

      [7]
    3. c)

      What are randomized algorithms? Enlist few reasons to use randomized algorithms.

      Also asked:May 2024

      [4]

  7. Q7

    1. a)

      Write a simple multithreaded matrix multiplication algorithm based on parallelizing relevant loops of the conventional procedure.

      [8]
    2. b)

      Explain in brief race condition in multithreaded algorithms.

      [4]
    3. c)

      What do you understand by spawn and sync keywords used in multithreaded programming?

      Also asked:May 2024

      [6]

  8. Q8

    1. a)

      Write distributed breadth search algorithm. What is its advantage over the conventional approach?

      [8]
    2. b)

      Write a Rabin-Karp string matching algorithm. Input to the algorithm be: Original text “t” of length n and pattern text being matched is “p” of length m. What is the expected runtime and worst-case runtime of this algorithm? … … …

      Also asked:Nov 2024 ·May 2024

      [10]