|
Sets of strings |
-
reads and writes pseudocode
-
describes basic ideas and time complexities of binary searching, balanced binary search trees, hashing and some sorting algorithms
|
-
describes basic ideas and time complexities of several string sorting algorithms and data structures for storing a set of strings
-
simulates several string sorting algorithms and draws data structures for storing a set of strings
|
-
describes general techniques for designing comparison-based algorithms or data structures for strings
-
proves simple results on longest common prefixes
|
-
applies the general techniques to design nontrivial comparison based algorithms and data structures for strings
-
implements string sorting algorithms and data structures for sets of strings
|
|
Exact string matching |
-
derives worst case time and space complexities of simple algorithms and describes the meaning of average case time complexity
-
describes the language recognized by simple deterministic and nondeterministic finite automata
|
-
describes basic ideas and time complexities of several exact string matching algorithms
-
simulates simple exact string matching algorithms and draws Morris-Pratt and Aho-Corasick automata
|
-
proves correctness and time complexities of simple exact string matching algorithms
-
chooses the approriate exact string matching algorithm for a given situation
-
adapts exact string matching algorithms to solve related problems such as multiple exact string matching and string matching with don't-cares
|
-
implements exact string matching algorithms that are competitive with the best implementations
-
analyzes average case complexities of exact string matching algorithms
|
|
Approximate string matching |
-
explains simple induction proofs
|
-
describes the basic recurrences for edit distance computation and approximate string matching
-
computes edit distance and solves approximate string matching by filling the dynamic programming table
-
describes the basic ideas of several faster algorithms for approximate string matching
|
-
derives a recurrence for a simple variant of edit distance
-
designs a filtering algorithm based on a given simple filtration condition
-
|
-
derives a recurrence for a complex variant of edit distance
-
uses advanced approximate string matching techniques for complex variants of edit distance
|
|
Suffix trees and arrays |
-
same as sets of strings and exact string matching
|
-
constructs the suffix tree, the suffix array and the LCP array for a given string
-
solves simple problems using suffix trees and arrays
|
-
describes several additional data structures associated with suffix trees and arrays
-
describes basic ideas of algorithms for constructing suffix trees and arrays
-
solves more complex problems using suffix trees and arrays
|
-
implements algorithms for constructing suffix trees and arrays and for solving problems using them
-
describes compressed text indexes
|