imp QP

[shashikala Hebbar]

-- 

1. Briefly explain the Rabin-Karp  alogorithm for the string T=  HERE IS SIMPLE EXAMPLE  and pattern P=SIMPLE                                                                 (10)

 

2. A. Prove the following:                                                                                             

i.                    For all n ³ 0, k ³ 0, and d > 0: w_dn^dk  = w_n^k.                                     (04)

ii.                  If n > 0 is even, then the squares of the n complex n^th roots of unity are the n/2 complex (n/2)^th roots of unity.

B. Write and explain how iterative FFT implementation computes the DFT_n(a) in time Q(n lg n).                                                                                                            (06)

 

3. Briefly, explain string matching with finite automata algorithm. Prove the correctness for the same.                                                                             (10)

 

4. With an example, write and explain Knuth-Moris-Pratt algorithm. Prove the correctness of the prefix-function computation.                                                (10)

 

5. Explain the different representation of polynomial with example. And also explain the need of each representation                                                                        (6+4)

 

6. Explain the following terms                                                               (3+3+4)
1. Degree in polynomial
2. Suffix Function
3. Degree bound

 

7. Briefly explain the Boyer-Moore algorithm good suffix function                (10)

Shashikala