Design and Analysis of Algorithm Unit 5 – Selected Topics: important questions for AKTU
Unit 5 (Selected Topics) questions that AKTU repeats most often. This unit carries about 29 marks per paper. Start with the repeated questions, then the most asked topics.
Most repeated Unit 5 questions
- 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, 2026, String Matching) – also asked in 2024, 2023, 2022
- Explain P, NP, NP –Complete and NP-Hard complexity classes. How they are related to each other. (7 marks, 2025, NP-Completeness Theory) – also asked in 2024, 2023, 2022
- 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, 2025, String Matching) – also asked in 2024, 2023, 2022
Most important Unit 5 topic
- String Matching (Unit 5: Selected Topics) – asked 13 times in 2019, 2020, 2021, 2022, 2023, 2024, 2025, 2026
Most asked Unit 5 topics
- String Matching – asked 13 times
- NP-Completeness Theory – asked 8 times
- Approximation Algorithms – asked 7 times
More Unit 5 previous year questions
- Define Polynomial-time Verifiability. (2 marks, 2026, NP-Completeness Theory)
- Describe the Boyer-Moore string matching algorithm. How do the bad character and good suffix heuristics work? (7 marks, 2026, String Matching)
- Describe “Randomized algorithms”. List few randomized algorithms. (2 marks, 2025, Randomized Algorithms)
- Explain Vertex Cover Problem. Solve vertex cover problem using approximation algorithm (7 marks, 2025, Approximation Algorithms)
- What do you mean by Boyer-Moore Algorithm? (2 marks, 2024, String Matching)
Unit 5 syllabus topics
- Algebraic Computation
- Fast Fourier Transform
- String Matching
- NP-Completeness Theory
- Approximation Algorithms
- Randomized Algorithms