Objectives

From the Course Objectives a key point is the objective to: critique, contrast, compare, and evaluate the efficiency, effectiveness, and utility of commercially available and research prototype systems for IS&R. We can operationalize this in terms of considering the PAT system and UNIX tools in the grep family. We can also look at the fundamental issues in this regard, involving data and files structures and their coupling with algorithms: building PAT trees and arrays, testing the many operations they support on real collections, and comparing the speed of various string matching schemes.

Another objective calls for students to: read and understand research contributions ... Certainly Chapter 5 is representative of the research literature, and Chapter 10 has some of that flavor as well as some of the attributes of a survey article.

In summary, this Unit has the following objectives, for students to be able to:

1. effectively use the PAT system for string searching and other types of text analysis;

2. explain how the PAT system carries out the operations available, referring to the relevant file and data structures;

3. explain the key ideas behind the various string search algorithms that have evolved in recent decades; and

4. compare and contrast the various string searching algorithms regarding complexity of code, efficiency, and utility for various types of patterns.