String Pattern Recognition - ATHENS Course (March 2011)
Project 1 : Linear-Time String Matching Algorithms - The Karp-Rabin Algorithm
DEADLINE: March 15th, 2011, 9:00 a.m.
1 Introduction
The goal of this pro ject is to study from an experimental point of view how the worst-case for the Karp-Rabin algorithm works. As seen in the theory lectures, the worst case depends on the number of false matches.
More specifically, goals of this project include:
- Reinforcement of the knowledge acquired by students about the Karp-Rabin.
- Deep understanding of the parameters associated with the Karp-Rabin algorithm, in particular, the choice of parameter q.
- Testing a string matching algorithm with data close to those found in practice.
- Actual programming of string matching algorithms.
- Conducting a computational experiment.
- Comparison of theoretical and experimental results.
- Interpretation of results and presentation of conclusions.
- Writing an academic paper.
2 The Karp-Rabin Algorithm
The Karp-Rabin algorithm must be implemented. That includes choosing all the parameters of the algorithm as well as taking into account on which computer or with which compiler is used. All
the chosen parameters must be justified according to the theory. Students will have to perform two experiments in this section.
Experiment 1 - Directions:
- Set Σ = {0, 1, . . . , 9} as the alphabet for the whole experiment. Assume that the word of computer is w = 32.
- Generate a text T1 of length n = 5, 000.
- Generate patterns of length m = 50 by randomly selecting substrings of T1 . Generate a hundred patterns in total.
- Solve then the SMC problem, that is, search for all the occurrences of each pattern in T1 with the Karp-Rabin algorithm. Keep track of the number of false matches.
- Consider the variable number of false matches per search. Perform a statistical analysis of the data. This analysis should include at least mean, variance, median, mode. Estimate the probability of a false match out of your statistical analysis. Use the statistical package of your choosing to make the analysis.
- Plot the data as a histogram. If necessary, use other graphical representations of data.
- Draw conclusions from the data gathered.
Experiment 2 - Directions:
- Repeat Experiment 1 this time setting q as the prime 4099.
- This includes repeating the statistical analysis.
- Draw conclusions from the data gathered. In particular, compare both data set and explain the influence of the choice of q on the algorithm’s performance. Show keen understanding of the algorithm will be highly appreciated.
3 Programming
Implementation of algorithms may be done in any language of student’s choice. However, the language and its compiler should support certain features in order to be able to run the experiments properly.
The choice of C, C++, Maple or the like should be enough. Source code and a .exe file have to be handed over.
4 Written Paper
A paper describing the following points must be handed over.
- Brief explanation of the algorithms.
- Brief explanation of the implementations. It can be done by including sufficiently detailed comments in the code.
- Brief description of the experiment.
- Interpretation of experimental data. Conclusions. Draw your own conclusions (be creative, but not extravagant or too showy).
The paper has to be written in correct English; it also has to possess clarity of thought. Show me what you know; do not force to search for it through a poorly written paper.
5 Grading
The whole project counts 50% of your programming final grade. I will take points off if:
- There are spelling mistakes.
- It has irrelevant material. Down with the irrelevant!
- It lacks clarity of thought.
- It is lengthy, long-winded or poor in content.
- Code is not properly commented.
- Code is not properly structured.
- Variables have absurd names.
- There are run-time errors.
6 Questions and Office Hours
I am willing to answer your questions about algorithms, complexity or the experiment. I will not answer questions about coding errors as it is my feeling that, at this point, writing error-free code is your responsibility.
