CSCI5454 Homework 2- Knuth-Morris-Pratt Alg., Divide-And-Conquer Algorithms (FFT) Solution

P1. (10 points) Suppose we are using KMP algorithm to match a pattern against a text and we do not find a pattern match. This problem asks you to modify the pseudo-code to find the longest prefix of the pattern that matches the text: output the ending position of the match in the text string and the length of the longest prefix match. If there are multiple matches of the same prefix length: you should find the earliest match in the test.
Modify the pseudocode below and write a very brief explanation of why your modification works. As always, you should implement this in your favorite language and test it thoroughly. But no need to submit code or report on that for this assignment.
Here is the pseudo-code for the original KMP algorithm as presented in class. Assume π is the table constructed as shown in class.
1 def kmp matcher( txt , pat , π ):
2 (n, m) = len( txt ) , len(pat )
3 i = −1 # i is the la st index processed in text 4 j = −1 # j is the la st index processed in pattern 5 while i < n−1 :
6 if pat [ j +1] == txt [ i +1]:
7 ( i , j ) = ( i + 1 , j + 1) 8 else :
9 if j == −1:
10 i = i + 1
11 else : 12 j = π[j]
13 if j == m −1 :
14 print( f ’ Pattern matched at position { i } ’ )
15 j = pi [ j ]
Your answers should present pseudo-code (python code is fine). Add a few lines of explanations but if your logic is clear, comments in the code can be an explanation. For our convenience, it would be great if you can highlight your changes in the pseudocode.
P2. (15 points) We have sets S1,S2 and S3 that are all subsets of {0,...,n − 1} for a number n > 0. Each set is given to you as an array of Booleans. Eg., for n = 5 and S1 = {1,2,4}, we have the array [0,1,1,0,1] that denotes the set S1.
(A, 7 points) Given a target number T, write an efficient algorithm to calculate the number of triples (i1,i2,i3) such that i1 ∈ S1, i2 ∈ S2 and i3 ∈ S3 such that i1 + i2 + i3 = T. Your algorithm must operate in running time O(nlog(n)).
(B, 8 points) Find the number of triples (i1,i2,i3) such that i1 ∈ S1, i2 ∈ S2 and i3 ∈ S3 such that i1 + i2− i3 = 0. Your algorithm must operate in running time O(nlog(n)).
For each part, the solution can be written out in at most 5 sentences. No need for pseudocode.
1
P3 (10 points) In class, we will be studying a divide and conquer algorithm with the following recurrence relation for its running time complexity on input of size n:
.
for some positive constants C0,C1. Prove that T(n) = Θ(n(logn)2).
2