Design and Analysis of Algorithms

Unit 5: Algorithm Miscellaneous

  • Q1). What do you mean by String matching ? Also explain string, sub string and proper sub string.
  • Q2). Explain Knuth-Morris-Pratt Algorithm and give its analysis.
  • Q3). Explain Naive string matching algorithm and also discuss its analysis.
  • Q4). Discuss the string matching with finite automata.
  • Q5). Write an algorithm for Rabin-Karp method. Also give a suitable example to explain it.
  • Q6). What do you mean by Approximation algorithm? Explain.
  • Q7). Define Vertex cover. What is vertex cover problem? Provide the approximation algorithm for vertex cover problem.
  • Q8). Explain the vertex cover problem. Also write algorithm for it.
  • Q9). Explain Travelling Salesman Problem(TSP) with the triangle inequality.
  • Q10). Write short note on Randomized algorithm.
  • Q11). Write the merit , de-merits and applications of Randomized algorithm.
  • Q12). What is NP-Complete problem? Give one example.
  • Q13). What do you mean by decision problem?
  • Q14). What is Fast Fourier Transformation(FFT)? How the recursive FFT procedure works? Explain.