Assignment 3 CSCE 350

Programming Assignment 3
CSCE 350 : Data Structures and Algorithms


Instructions:
• The solutions should be very clear and should follow the instructions below and the requirements
stated for each problem.
• If you refer to any resource to get your solutions, add an acknowledgement with your solutions (details
of the source, e.g., book, website, etc.).
• All the codes should be written in c or c + + or JAVA for linux and commented appropriately for
major steps/functions.
• Code that does not compile will not be graded and get a 0 automatically.
• The codes should be submitted as a single zipped file through Blackboard
Part A:
1. Implement Horspool’s String Matching Algorithm using C or C++ or Java. (100 pts)
Requirements:
(a) Your code should be able to read an input ASCII file named ‘input.txt’, where the first line
contains the string of pattern, and the second line contains the string of text
(b) You can assume that all characters in both the pattern and text belong to 26 letters of English
alphabet plus the space
(c) Your code will produce an output ASCII file named ‘output.txt’, which contains the index of the
left end of the first matching substring or -1 if no match
(d) Your code should output the execution time for running the algorithm excluding time of input/output.
(e) A script file or readme file including the instructions to compile and run the code should be
submitted together with the codes
Bonus question: Implement Boyer-Moore’s String Matching Algorithm using C or C++ or Java (40
pts) Requirements:
1. Your code should be able to read an input ASCII file named ‘input.txt’, where the first line contains
the string of pattern, and the second line contains the string of text
2. You can assume that all characters in both the pattern and text belong to 26 letters of English alphabet
plus the space
3. Your code will produce an output ASCII file named ‘output.txt’, which contains the index of the left
end of the first matching substring or -1 if no match
4. Your code should output the execution time for running the algorithm excluding time of input/output.
5. A script file or readme file including the instructions to compile and run the code should be submitted
together with the codes
2