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): (15351 or 15650 or 02613 or 15210) and (15151 or 21127)
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%)