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

Questions

1. Q1

   1. a)

      You are given a set of tasks, each with a deadline and a penalty for missing the deadline. The objective is to schedule these tasks in a way that minimizes the total penalty incurred. However, you can only work on one task at a time, and once a task is started, it must be completed before moving on to the next task. Additionally, you can't start a task after its deadline has passed. Design a greedy algorithm to efficiently schedule these tasks to minimize the total penalty and prove its correctness.

      [8]
   2. b)

      Suppose we have a knapsack with a maximum weight capacity of 15 units, and we have the following items with their respective weights (Wi) and values (Vi) : Objects Weight Value O1 8 10 O2 6 8 O3 4 3 O4 2 4 Use greedy approach to maximize the total value of items we can put into the knapsack without exceeding its weight capacity.

      [8]
   3. c)

      With respect to dynamic programming, what do you understand by optimal substructure? 2

      [2]
   OR

2. Q2

   1. a)

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

      [10]
   2. b)

      Under what situation do you think the dynamic programming approach for solving a knapsack problem might struggle to find the optimal solution? Briefly explain.

      [4]
   3. c)

      Enlist the uses of writing control abstraction for any algorithmic strategies.

      [4]

3. Q3

   1. a)

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

      [8]
   2. b)

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

      [9]
   OR

4. Q4

   1. a)

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

      [8]
   2. b)

      Write a short note on LC branch and bound method.

      [5]
   3. c)

      What are the drawbacks of branch and bound method?

      Also asked:May 2025

      [4]

5. Q5

   1. a)

      What are the advantages and disadvantages of : i) Aggregate Analysis ii) Accounting Method

      [8]
   2. b)

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

      Also asked:May 2024

      [9]
   OR

6. Q6

   1. a)

      Why potential function method cannot be used for analysing binary counter? Explain

      [8]
   2. b)

      Comment on the following statements : i) “The knapsack problem is NP-hard” ii) “Boolean Satisfiability Problem (SAT) is NP-complete” iii) “Minimum spanning tree is tractable problem” 4

      [9]

7. Q7

   1. a)

      Write a Rabin-Karp string matching algorithm. Let 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 ·May 2024

      [10]
   2. b)

      Briefly explain performance measures – speedup, efficiency, throughput, contention, and latency of rnultithreaded algorithms.

      [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)

      If we have two matrices of the order m x n and n x p then what will be the time complexity of multiplying these matrices in conventional approach and in multithreaded approach. Discuss. ♦♦♦

      [8]