Skip to content
EndsemNov 20232019 patternBE Comp

Design & Analysis of Algorithms (DAA) SPPU Endsem Question Paper Nov 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
Nov 2023
Max. marks
70
Time
2½ Hours
Semester
I
Paper code
[6181]-101

Printed for: B.E. (Computer Engineering)

Instructions to the candidates

  1. Answer Q1 or Q2, Q3 or Q4, Q5 or Q6, Q7 or Q8.
  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)

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

      [9]
    2. b)

      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:May 2023

      [9]

  2. Q2

    1. a)

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

      [12]
    2. b)

      Write steps for Greedy approach for Job sequencing. 2

      [6]

  3. Q3

    1. a)

      What is branch and bound algorithmic strategy? Apply branch n bound algorithmic strategy to solve traveling salesman problem for

      [9]
    2. b)

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

      Also asked:May 2023 ·Nov 2022

      [8]

  4. Q4

    1. a)

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

      [9]
    2. b)

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

      [8]

  5. Q5

    1. a)

      What is amortized analysis? Explain the aggregate method with example.

      Also asked:Nov 2025 ·May 2025 ·May 2024

      [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:May 2023 ·Nov 2022

      [9]

  6. Q6

    1. a)

      What are special needs of embedded algorithm? Which sorting algorithm is best for embedded systems? Why?

      [6]
    2. b)

      Explain Randomized and Approximate algorithms. 3

      [4]
    3. c)

      What is randomized algorithm? Give any example of randomized algorithm? Also explain Random variable, Binomial random variable and-Mathematics for Randomized algorithm.

      [8]

  7. Q7

    1. a)

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

      Also asked:May 2023

      [10]
    2. b)

      With respect to Multithreaded Algorithms explain Analyzing multithreaded algorithms, Parallel loops, Race conditions.

      Also asked:Nov 2022

      [7]

  8. Q8

    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:May 2023 ·Nov 2022

      [9]
    2. b)

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

      [8]