| Principal theme | Prerequisite knowledge | Approaches the learning objectives | Reaches the learning objectives | Deepens the learning objectives |
|---|---|---|---|---|
|
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 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 |
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 |
describes compressed text indexes |