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.
