# 58093 String Processing Algorithms (luonnos 22.12.2014)

Pääteemat Esitiedot Lähestyy oppimistavoitetta Saavuttaa oppimistavoitteet Syventää oppimistavoitteita
Sets of strings
• 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

22.12.2014 - 23:41 22.12.2014 - 23:41