Skip to content
EndsemMay 20232019 patternBE Comp

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

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 2023
Max. marks
70
Time
2½ Hours
Semester
VII
Paper code
[6004]-480

Printed for: B.E. (Computer Engineering)

Instructions to the candidates

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

Questions

  1. Q1

    1. a)

      Consider the following instance of the knapsack problem. Find the optimal solution by using dynamic programming approach. Item Weight Profit 1 2 $12 2 1 $10 3 3 $20 4 2 $15 Capacity of the knapsack = 5.

      Also asked:Nov 2023

      [10]
    2. b)

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

      [8]

  2. Q2

    1. a)

      What is greedy approach? Explain Job scheduling algorithm using Greedy approach for following examples. Give the sequence of job scheduling. 2 Input: Four jobs with following deadlines and profits Job1D deadline Profit a 4 20 b 1 10 c 1 40 d 1 30 Input: Five Jobs with following deadlines and profits Job1D Deadline Profit a 2 100 b 1 19 c 2 27 d 1 25 e 3 15

      [8]
    2. b)

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

      [10]

  3. Q3

    1. a)

      Explain with suitable example Backtracking: Principle, control abstraction, time analysis of control abstraction.

      Also asked:Nov 2023 ·Nov 2022

      [8]
    2. b)

      Compare between greedy method and dynamic programming with respect to. i) Feasibility. ii) Optimality. iii) Recursion. iv) Memorization. v) Time complexity.

      [9]

  4. Q4

    1. a)

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

      [8]
    2. b)

      What is Branch and Bound method? Write control abstraction for Least cost search? 3

      Also asked:Nov 2022

      [9]

  5. Q5

    1. a)

      What is amortized analysis? Explain aggregate and potential function methods used for amortized analysis with respect to stack operations?

      [9]
    2. b)

      What is potential function method, of amortized analysis? To illustrate potential method, find amortized cost of PUSH, POP and MULTIPOP stack operations.

      Also asked:Nov 2023 ·Nov 2022

      [9]

  6. Q6

    1. a)

      Write short notes on the following. i) Aggregate analysis. ii) Accounting Analysis. iii) Potential function method. iv) Tractable and Non-tractable problems.

      Also asked:Nov 2022

      [10]
    2. b)

      Write short notes on with suitable example of each. i) Randomized algorithm. ii) Approximation algorithm.

      Also asked:Nov 2022

      [8]

  7. Q7

    1. a)

      Write and explain pseudo code for multi-threaded merge sort algorithm. How parallel merging gives a significant parallelism advantage over merge Sort?

      Also asked:Nov 2023 ·Nov 2022

      [9]
    2. b)

      i) Explain an algorithm for Distributed Minimum Spanning Tree. ii) Write and explain Rabin-Karp algorithm for string matching.

      Also asked:Nov 2023

      [8]

  8. Q8

    1. a)

      Write short notes on the following. i) Multithreaded matrix multiplication. ii) Multithreaded merge sort. iii) Distributed breadth first search. iv) The Rabin-Karp algorithm.

      Also asked:Nov 2022

      [10]
    2. b)

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

      [7]