Design & Analysis of Algorithms (DAA) SPPU Endsem Question Paper May 2024

Questions

1. Q1

   1. a)

      Write a control abstraction for greedy method. Comment on the time complexity of this abstraction?

      [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 “Problem which does not satisfy the principle of optimality cannot be solved by dynamic programming”.

      [4]
   OR

2. Q2

   1. a)

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

      Also asked:Nov 2025

      [8]
   2. b)

      Consider 4 matrices A1, A2, A3 and A4. The orders of these matrices are given below: Matrix Order A1 3×5 A2 5×4 A3 4×2 A4 2×4 Find the optimal sequence of chain matrix multiplication of these matrices using dynamic programming approach. Clearly give the final sequence and total number of multiplications involved. 2

      [10]

3. Q3

   1. a)

      Assume that a graph with n vertices is represented by an adjacency matrix G. Let there be “m” number of colours available. Write a recursive backtracking algorithm to colour all the vertices of the graph. What is the time complexity of this algorithm?

      [8]
   2. b)

      Consider three items along with respective weights and value as Weight Value Value/Weight O1 5 6 6/5 = 1.2 O2 4 5 5/4 = 1.25 O3 3 4 4/3 = 1.3 Assume the Knapsack capacity m = 7. Solve this 0/1 Knapsack problem using LC branch and bound method.

      [9]
   OR

4. Q4

   1. a)

      Compare backtracking with branch and bound method with respect to: search technique, exploration of state space tree and king of problems that can be solved.

      [8]
   2. b)

      Consider 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 subject is equal to 30. Solve this problem to find the first solution using backtracking approach. Show space tree being created.

      Also asked:Nov 2025

      [9]

5. Q5

   1. a)

      What are randomized algorithms? Enlist and explain in brief the primary reasons for using randomized algorithms.

      Also asked:May 2025

      [8]
   2. b)

      What are approximation algorithms? Based on the approximation ratio, classify the approximation algorithms.

      Also asked:Nov 2024

      [9]
   OR

6. Q6

   1. a)

      Explain the methods of amortized analysis. Give suitable example.

      Also asked:Nov 2025 ·May 2025 ·Nov 2023

      [8]
   2. b)

      Suppose you are working on an embedded system for a medical device that monitors patient vital signs. The device continuously collects data from various sensors and needs to process and display this information in real-time. The data includes timestamps, temperature readings, heart rate, and blood pressure measurements. Suggest suitable sorting algorithm for this scenario. Clearly justify your answer with respect to key factors. 3

      [9]

7. Q7

   1. a)

      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:May 2025 ·Nov 2024

      [10]
   2. b)

      Write multi-threaded merge sort algorithm. Briefly discuss how does it differ from conventional merge sort.

      [8]
   OR

8. Q8

   1. a)

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

      [10]
   2. b)

      What do you understand by spawn and sync keywords used in multithreaded programming? Explain with the help of suitable example. 

      Also asked:May 2025

      [8]