Theoretical and Empirical Analysis of String Matching Algorithms DEADLINE: Feb 02" 2023, 23:59. 1. Introduction In this project, you are requested to analyze and implement widely used string matching algorithms. Your input will be a corpus of existing documents and a pattem you are looking for. Your output will be the set of documents that contain your query pattern. You will be working in a team of two students to fulfill the project requirements. 2. Project requirements You are required to compare string matching algorithms both from a theoretical and experimental point of view. The intended goals include: - Acquisition of knowledge about specific string matching algorithms. - Programming of the considered algorithms. - Conducting computational experiments. - Interpretation of the obtained result. - Writing a technical report. 3. String matching algorithms Analyze and implement the following string matching algorithms and compare their performance: a. Brute force algorithm. b. Knuth-Morris-Pratt's algorithm (KMP). c. Boyer-Moore's algorithm. You have to conduct a research to understand those algorithms. Your tutorial instructor can then answer further questions if any. 4. Experiments Experiments have to be carried out acconding to the following directions. 1. Each algorithm has to be run on test documents that are randomly generated. Hint: Java classes such as RandomStringUtils, java.util.UUID and Math include simple methods that can be used to generate Numeric, Alphabetic, AlphaNumeric strings. 2. Each algorithm has to run on a text document of size n (number of characters), where n varies from 100 to 10,000 and increases by 100 cach time (that is, n=100,200,,10,000 ). 3. Each algorithun must be ran on iest data five time. The reported rua times are then de averuge of those five runs. 4. Running times will be plotted against input size. 5. From the plots, the input size for which an algorithm is faster than another will be estimated. 5. Programming The implementation of algorithms must in Java, and the source code has to be handed over. 6. Project demonstrations Once the project is completed, the following is expected of you: a. A demonstration video (5 to 10 minutes) of your project where you show the various features of your system, such as its correctness, efficiency, etc. You should provide all details on the system design and implementation during this demo. Your code will be examined to check for code quality, code documentation, etc. b. You should also hand in a completed project report which contains details about your project, such as main data structures, main components of the algorithm, design of the userinterface for input/output, experimental results, eg charts of running time versus input size, ete. c. You should also turn in your code and associted documentation (e.g. README files) so that everything can be backed up for future reference. d. Email your code and all associated files to your tutorial instructor with "CSC 311 Project> " as sabject