CS5604, Unit SS

Edward A. Fox
Department of Computer Science, Virginia Tech, Blacksburg VA 24061-0106

Abstract:

Most computer users undertake some type of searching: in a text editor, with utilities like grep, or with special search systems. We begin with the most powerful string search system that is presently available, PAT - studying its use and the underlying algorithms and data structures. Chapter 5 explains these in detail, and a lecture provides clarification. The PAT User's Guide [1] and related exercises allow us to achieve a good working knowledge of the underlying model and its implementation.
Common string searching, on the other hand, simply takes a pattern and tries to find match(es) in a target string. Since this is such an important operation, fast algorithms are critical. Chapter 10 surveys the numerous algorithms, considers their strengths and weaknesses, and gives empirical performance data. Practice with the grep family of UNIX commands reinforces these results. The xtango package helps clarify the operation of the KMP and Boyer-Moore algorithms.
This Unit has 2 chapters, 2 exercises, 2 lectures, and a session in the laboratory (September 29).

fox@cs.vt.edu
Thu Oct 6 15:01:34 EDT 1994