Carnegie Mellon University

String Algorithms

Course Number: 02-414

Key Topics: 

  • string search
  • inexact matching
  • string compression
  • string data structures such as suffix trees, suffix arrays, and searchable compressed indices
  • the Burrows-Wheeler transform
  • locality sensitive hashing
  • de Brujin Graphs

Units: 12
Prerequisite(s): 15-210; 15-151 or 21-127

Learning Objectives

  • Learn various algorithmic techniques and data structures for efficient processing of string data, including suffix trees,suffix arrays, Borrows-Wheeler transforms.• Understand the why these algorithms and data structures work.
  • Learn to apply and extend these algorithms and data
    structures.
  • Learn about the practical application of these techniques,
    especially in genomics
  • At the end of this class, you should be familiar with much of the state-of-the-art in algorithms for strings, have familiarity with their use in practice, and have experience applying them to new problems.

Assessment Structure: 

  •  Homework assignments (35%)
  • 2 Midterm exams (15% each)
  • Final exam (25%)
  • Class participation and quizzes (10%)