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 n²/2-3n= Q(n²)    (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)