Pattern Matching & Back-of-the-Envelope Esti- mations 4 The pattern matching problem can be stated as: (10 pts) Given a

[answerhappygod]

Pattern Matching Back Of The Envelope Esti Mations 4 The Pattern Matching Problem Can Be Stated As 10 Pts Given A 1 (186.99 KiB) Viewed 31 times

Pattern Matching & Back-of-the-Envelope Esti- mations 4 The pattern matching problem can be stated as: (10 pts) Given a (usually long) text string t and a (usually shorter) pattern p find where or if the pattern p occurs in t. Assume the length of t is n and the length of p is m Several algorithms were presented in the course notes to solve the pattern matching problem Here are two: • Brute-Force: The notes state the time complexity of this approach to solving the problem is O(mn). • Knuth-Morris-Pratt: The notes state the time complexity of this approach to solv- ing the problem is 0(m + n). The human genome is approximately three billion base pairs in size. the average length of a gene is approximately 30 thousand base pairs. Let m 30, 000 and n = 3,000,000,000 There are about 30, 000, 000 seconds in a year. Assume a character-to-character comparison takes 1 microsecond. Estimate the time it will take to run a brute-force algorithm. Do the same for the KMP algorithm.