Course Overview

Having grown accustomed to the wealth of the entire internet at our fingertips it is hard to remember that a mere 25 years ago, an encyclopedia on a CD was the height of information technology available to the individual! It is astounding that a few decades ago billions of dollars were invested by governments and industry for mapping the first human genome whereas today one can purchase his DNA on a flash drive for a few thousand dollars.

Some of the key algorithmic tools in these endeavors were pattern matching algorithms. Pattern matching problems are among the oldest in computer science. For example, Celera Genomics used shotgun sequencing to complete the first sequenced genome. Every text editor, from Office to Emacs uses the Boyer-Moore algorithm. Yet, the area is still a fertile ground for very active current research. Part of its appeal is in its many application domains, such as text editing, image processing, music analysis, or molecular biology. Some concrete examples follow. Google uses pattern matching algorithms for indexing images. The app Soundhound for detecting music, requires heterogeneous indexing. Pattern matching algorithms are used for detecting malware, such as from the SNORT database, in data streams. Indeed, pattern matching algorithms served as building blocks for major projects in the past and will continue to be invaluable in the future.

Another important aspect of the field is that pattern matching has produced or incorporated some novel and powerful algorithmic techniques and is likely to continue to be a catalyst for new data structures and algorithmic techniques. These techniques are general, transportable, and scalable, thus can be used to solve myriad tasks in heterogeneous searching and indexing.

Course participants will learn these topics through lectures and assignments. The classes will be transcribed by the students.

For a detailed schedule of lectures, please click here. The materials will be made available to all registered students via the Canvas interface. More details will be available soon.