Design and Analysis of Algorithm Unit 5 Notes AKTU (BCS503)

AKTU · BTECH · Semester 5 · Design and Analysis of Algorithm · Unit 5 · Notes

AKTU Design and Analysis of Algorithm (BCS503) Unit 5 notes for B.Tech Semester 5 – Selected Topics. Topics: Algebraic Computation, Fast Fourier Transform…

Open the interactive reader to study this resource on AcademicArk.

Unit 5: Selected Topics – AKTU syllabus topics

  • Algebraic Computation
  • Fast Fourier Transform
  • String Matching: Naive String Matching, Rabin-Karp Algorithm, Knuth-Morris-Pratt Algorithm, Boyer-Moore Algorithm, Cyclic Rotation Matching
  • NP-Completeness Theory: Polynomial Time Verifiability
  • Approximation Algorithms
  • Randomized Algorithms

Most asked AKTU PYQ questions from Unit 5

  1. Q1j. Explain NP-complete and NP-Hard. (2 marks, 2021-22)
  2. Q1g. Define Polynomial-time Verifiability. (2 marks, 2025-26)
  3. Q7b. Explain KMP matcher and also implement it by an algorithm, where P=a,a,b,a,b,b,a and T=b,a,b,a,a,b,a,b,b,a (10 marks, 2023-24)
  4. Q7a. Explain P, NP, NP Hard and NP Complete Classes with example. (10 marks, 2023-24)
  5. Q7a. What is string matching algorithm? Explain Rabin-Karp method with examples. (10 marks, 2022-23)
  6. Q7a. Write short notes on following: (i.) Randomized algorithm. (ii.) NP- complete and NP hard. (10 marks, 2020-21)
  7. Q7a. Using Rabin-Karp algorithm, how many hash computations are needed to search for a pattern of length 4 in a text of length 15? (7 marks, 2025-26)
  8. Q7a. Explain P, NP, NP –Complete and NP-Hard complexity classes. How they are related to each other. (7 marks, 2024-25)
  9. Q7b. Write Knuth-Morris-Pratt string matching algorithm. Take a suitable example Compute the prefix function π for the pattern ababbabbabbababbabb when the alphabet is Σ = {a, b}. (7 marks, 2024-25)
  10. Q1j. Explain Randomized algorithms. (2 marks, 2022-23)

AKTU paper codes: BCS503, KCS503, RCS502

Other Design and Analysis of Algorithm units

Design and Analysis of Algorithm previous year papers

More Design and Analysis of Algorithm resources

Browse all notes · Semester 5 notes