Term Paper: Strings Matching
String matching is a fundamental string problem that has many important
applications. For example, Internet search engines such as Google use
string matching algorithms to find related documents that contain
certain keywords. In this paper
you are asked to research on such algorithms. Given a string P called
the pattern and a longer string T called the text, the exact matching
problem is to find all occurences, if any, of pattern P in text T. For
example, if P=aba and T=bbabaxababay then P occurs in T starting at
locations 3, 7, and 9.
Objectives
- understand a given problem
- describe and analyze an algorithm designed by yourself using the
techniques in our class
- learn to wade through a research work process: how to collect
data, select and analyze information, understand algorithms
through an example, and finally writing clearly
- familiar yourself with a publication format in the field
- abilities to improve: creativity, analyzing, understanding,
and writing
Contents
-
design an algorithm (pseudocode)
of your own before
reading any
references. Give a time/space complexity analysis and some comments
about
its implementations or other aspects (advatages, disadvantages, etc.)
-
give at least two efficient (you think best) algorithms in the
literature
and do the same (pseudocode, complexity, and comments); compare these
algorithms
with yours. You can collect information from books, magzines,
conference proceedings, and Internet, etc. Library is a nice source to
start with.
-
use one (the same) particular example (e.g. use above P and T) to
illustrate all abovementioned algorithms; however, you don't have to
implement (code and test) these algorithms.
Requirements and Formats
-
direct copying without quotes ("...") are regarded as plagarism (kind
of
cheating). Such an instance will lead to a zero score for this
assignment.
Therefore, you must be very careful. Remember to point to the
references
for the ideas from somewhere else instead of your own.
-
10-15 pages of 12-point fonts and 1.5 lines spacing (typing is required
using some software e.g. WORD or LaTex). Email me your file (named
YOUR_LAST_NAME.doc).
-
at least 5 references
- Format your paper as
this Skip Lists
paper except the spacing, font size, pages (you may use one column
only).