This project was the final assignment for the class Algorithms that I completed at WPI in the last term of my freshman year. This project involved a team of five people (myself, Garret, Pooja, Isabel, Adi, and I) researching the KMP substring search algorithm. The assignment entailed us creating a report on the algorithm and performing empirical tests on it in Java, recording the results and constructing graphs to find trends.
I wrote the testing suites we used on the KMP algorithm. These suites tested three parts of the algorithm- different word lengths, different pattern lengths, and different alphabets. The KMP algorithm was tested against the brute force substring search algorithm, as can be seen in the below source code.
The first code sample is the test suites that I wrote and ran on the two substring search algorithms, which were implemented by the following two samples. The KMP Algorithm file was taken from the textbook, while the Brute Force file was created by my teammates (Garret, Pooja, Isabel, and Adi).
Below is the research paper my group and I wrote and turned in.