Unit 7
Algebric Computation, Fast Fourier Transform, String Matching, Theory of NP-Completeness, Approximation Algorithm, Randomized Algorithm.
University Questions are from
(AKTU, IPU, DTU, MDU, LPU, VIT, SRM, Amity, PU, JMI and many more…)
Design & Analysis of Algorithm
Assignment 1
Q – Write Knuth-Morris-Pratt algorithm for string matching.
Q – Show that Hamiltonian cycle is in NP class of problems.
Q – What are approximation algorithms? What is meant by a P(n) approximation algorithm for travelling salesman problem.
Q – Write short notes on the Fast fourier transform.
Q – Discuss the relationship between the class P, NP, NP-complete and NP-hard with suitable example of each class.
Design & Analysis of Algorithm
Assignment 2
Q – Discuss the decision problems of class P and NP.
Q – What are approximation algorithms? What is meant by a P(n) approximation algorithm for travelling salesman problem.
Q – Explain Boyer-Moore algorithm for string matching for text: “ a b c a a b c c a a b b a b c a”, Pattern “a b c”.
Compute worst case complexity of this algorithm.
Q – Write short notes
(a) Approximation of a NP-complete problem.
(b) Randomized sorting algorithm.
(c) Proving the problem of finding maximum clique of a graph to be NPC.
(d) Problem classes and their implications.
(e) Maximum Flow problem.
(f) Knuth-Morris-Pratt algorithm for pattern matching.
Q – What is string matching algorithm? Explain Rabin-Karp method with examples.
Design & Analysis of Algorithm
Assignment 3
Q – What do you mean by polynomial time reduction?
Q – Define NP hard and NP complete problems. What are the steps involved in proving a problem NP complete? Specify the problems already proved to be NP complete.
Q – Describe in detail Knuth-Morris_Pratt string matching algorithm. Compute the prefix function π for the pattern ababbabbabbababbabb when the alphabet is Σ = {a, b}.
Q – Write an algorithm for naïve string matcher?
Q – What is travelling salesman problem (TSP)? Find the solution of following TSP using dynamic programming.
0 | 1 | 15 | 6 |
2 | 0 | 7 | 3 |
9 | 6 | 0 | 12 |
10 | 4 | 8 | 0 |
Design & Analysis of Algorithm
Assignment 4
Q – Write KMP algorithm for string matching? Perform the KMP algorithm to search the occurrences of the pattern ‘abaab’ in the text string ‘abbabaabaabab’.
Q – Give a linear time algorithm to determine if a text T is a cycle rotation of another string T’. For example, ‘RAJA’ and ‘JARA’ are cyclic rotations of each other.
Q – Explain Approximation and Randomized algorithms.
Q – Differentiate NP complete with NP hard.
Q – Show the comparisons the Naive-String matcher makes for the pattern P = {10001} in the text T = {0000100010010} and also show that worst case time to find the first occurrence of a pattern in a text is O(n-m+1) (m-1).
Design & Analysis of Algorithm
Assignment 5
Q – Explain and write the Naïve-String matching algorithm: Suppose the given pattern p = aab and given text T = acaabc. Apply Naïve-String matching algorithm on above pattern (P) and Text (T) to find the number of occurrences of P in T.
Q – Explain and write Knuth-Morris-Pratt algorithm for pattern matching and also comment on its running time.
Q – Discuss the problem classes P, NP and NP complete with class relationship.
Q – What is FFT (Fast fourier transform)? How the recursive FFT procedure works? Explain.
Q – Describe approximation algorithm in detail. What is the approximation ratio? Give an approximation algorithm for the Travelling Salesman.
Design & Analysis of Algorithm
Assignment 6
Q – Define NP hard and NP complete problems. What are the steps involved in proving a problem NP complete? Specify the problems already proved to be NP complete.
Q – Write short note on Fast Fourier Transform (FFT).
Q – What is approximation algorithm? Explain set cover problem using approximation algorithm. Show that vertex cover problem is 2 approximate.
Q – Explain and write the Naïve-String matching algorithm: Suppose the given pattern p = aab and given text T = acaabc. Apply Naïve-String matching algorithm on above pattern (P) and Text (T) to find the number of occurrences of P in T.
Q – What are 4 types of string matching algorithm?
Design & Analysis of Algorithm
Assignment 7
Q – What is travelling salesman problem (TSP)? Find the solution of following TSP using dynamic programming.
0 | 1 | 15 | 6 |
2 | 0 | 7 | 3 |
9 | 6 | 0 | 12 |
10 | 4 | 8 | 0 |
Q – Describe in detail Knuth-Morris_Pratt string matching algorithm. Compute the prefix function π for the pattern ababbabbabbababbabb when the alphabet is Σ = {a, b}.
Q – Construct the string matching automaton for the pattern P = a a b a b and illustrate its operation on the text string T = a a a b a b a a b a a b a a b.
Q – Explain Boyer-Moore algorithm for string matching for text: “ a b c a a b c c a a b b a b c a”, Pattern “a b c”.
Compute worst case complexity of this algorithm.
Q – Explain Approximation and Randomized algorithms.