Feel free to discuss and help each other out, but does not imply that you can give away your code or your answers! Make sure to read all instructions before attempting this lab. You can work with a lab partner and submit one lab package for your group.
You must use an appropriate provided template from Canvas or my website (zeus.mtsac.edu/~tvo) and output "Author: Your Name(s)" for all your programs. If you are modifying an existing program, use "Modified by: Your Name(s)".
Exercise 1: Try BM and KMP pattern matching (code is pretty much given) on various T and P and them modify the code to count the number of comparisons. Use a driver to check them out. Make sure to understand the algorithms.
Try the following test cases:
T: “a pattern matching algorithm”, P: “rithm, P: “rithn”
T: “GTTTATGTAGCTTACCTCCTCAAAGCAATACACTGAAAA”, P:
“CTGA”, and P: “CTGG”
Exercise 2: Implement Brute Force Pattern Matching as described in textbook. Don’t forget to count the number of comparisons and you can use the same driver from above. It is best to run the same test cases for all three algorithms.
Lab question 1: Are there any situations where BM better than KMP? Explain.
Lab question 2: Is Brute Force Pattern Matching with BM’s looking-glass heuristic always better than original Brute Force Pattern Matching? Explain.
Extra Credit: Implement Brute Force Pattern Matching with BM's looking-glass heuristic. Don’t forget to count the number of comparisons and you can use the same driver from above. It is best to run the same test cases for all algorithms.
Online Submission: Submit one PDF file via Canvas includes status, answers to lab questions, output and source code for all required programs.
