Exact string matching

reads and writes pseudocode

basics of algorithm analysis

basics of finite automata

describes the principle of at least two exact string matching algorithms

knows the time complexities and limitations of the main exact string matching algorithms

analyses the average time complexity of exact string matching algorithms

Approximate string matching

dynamic programming

proof by induction

computes edit distances and solves approximate string matching problems

knows at least one technique for speeding up approximate string matching

uses dynamic programming to solve new
variations of approximate string matching

knows several techniques for speeding up approximate string matching

knows advanced techniques for approximate string matching

String sorting

basic sorting algorithms and their time complexities

Ω(n log n) lower bound
on comparison-based sorting

writes pseudocode for at least one string sorting algorithm

knows the time complexities and limitations of the main string sorting algorithms

adapts any simple standard sorting algorithm for sorting strings efficiently

analyses the cache complexity of string sorting algorithms

Sets of strings

binary search trees and binary search

draws basic string search trees for a given set of strings

knows the time and space complexities and limitations of string search trees and string binary search

knows external memory search trees for strings

Suffix data structures

basics of recurrence equations

constructs the suffix tree and suffix array for a given string

describes how to solve simple  problems using suffix tree or suffix array

uses suffix trees, suffix arrays and
additional data structures to solve
more complex problems

describes compressed text indexes