DAA Unit 5: Selected Topic Previous year questions

  1. What do you mean by String matching ? Also explain string, sub string and proper sub string.
  2. Explain Knuth-Morris-Pratt Algorithm and give its analysis.
  3. Explain Naïve string matching algorithm and also discuss its analysis.
  4. Discuss the string matching with finite automata.
  5. Write an algorithm for Rabin-Karp method. Also give a suitable example to explain it.
  6. What do you mean by Approximation algorithm? Explain.
  7. Define Vertex cover. What is vertex cover problem? Provide the approximation algorithm for vertex cover problem.
  8. Explain the vertex cover problem. Also write algorithm for it.
  9. Explain Travelling Salesman Problem(TSP) with the triangle inequality.
  10. Write short note on Randomized algorithm.
  11. Write the merit , de-merits and applications of Randomized algorithm.
  12. What is NP-Complete problem? Give one example.
  13. What do you mean by decision problem?
  14. What is Fast Fourier Transformation(FFT)? How the recursive FFT procedure works? Explain.