Skip to content
EndsemNov 20222019 patternBE Comp

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

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 2022
Max. marks
70
Time
2½ Hours
Semester
VII
Paper code
[5927]-342

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. Figures to the right side indicate 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.

      [10]
    2. b)

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

      Also asked:Nov 2023 ·May 2023

      [8]

  2. Q2

    1. a)

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

      [10]
    2. b)

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

      Also asked:Nov 2023 ·May 2023

      [8]

  3. Q3

    1. a)

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

      [9]
    2. b)

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

      Also asked:Nov 2023 ·May 2023

      [8]

  4. Q4

    1. a)

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

      Also asked:May 2023

      [9]
    2. b)

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

      [8]

  5. Q5

    1. a)

      Write short notes on the following. i) Aggregate Analysis ii) Accounting Method iii) Potential Function method iv) Tractable and Non-tractable Problems

      Also asked:May 2023

      [10]
    2. b)

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

      Also asked:May 2023

      [8]

  6. Q6

    1. a)

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

      [9]
    2. b)

      What is embedded algorithm? Explain Embedded system scheduling using power optimized scheduling algorithm. 3

      [9]

  7. Q7

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

      [10]
    2. b)

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

      Also asked:Nov 2023

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

      [9]
    2. b)

      Write a pseudo code for naïve string matching algorithm and Rabin- Karp algorithm for string matching and analyze the same. 

      [8]