# CSE408 : Design And Analysis of Algorithms CA Test 1 | Class Test | Continuous Assessment (CA) | Academic Task 1 | LPU

Set: A

Time Allowed: 45 Min                                                                                                                      M.M. 30

Q1. What are asymptotic notations? Explain Big-Oh notation in detail. Prove that n2/2-3n= Q(n2)    (10)

Q2. Using Rabin karp string matching algorithm match the given pattern P with given string S.
P = 745
S = 745727457                                                                            (10)

Q3. Write KMP algorithm (both Prefix and Matching functions)                           (10)

Set: B

Time Allowed: 45 Min                                                                                                                      M.M. 30

Q1. What do you mean by analysis of algorithms.  Explain Big Omega notation in detail. Show that 2 n^2 - n + 17 = Omega(n^2).                                                                                                             (10)

Q2. Write and explain Rabin Karp string matching algorithm                         (10)

Q3. Using KMP string matching algorithm, find the occurrence of the given patter P in the given text T.
T ß ABABACAB
P ß ABAB                                                                                                                 (10)