CSE6409

---

Stringology

3 Credit Hour Course

Intended For Level 0 Term 0 Students

Prerequisite:

Introduction to Stringology: Notations, Problems and Naive Solutions, Motivations, Applications, Basic string searching algorithms; Data structures for String Matching: Suffix Tree, Suffix Array, Aho-Corasick Automaton, Applications of these data structures; Approximate Pattern Matching: Edit distance, Dynamic programming, Similarity measures for DNA and protein sequences, q-gram methods, Bit-parallel methods, Algorithms for degenerate/indeterminate strings; Sequence Analysis: Longest Common subsequence (LCS) Problem, Advanced Algorithms for LCS, Variants of LCS and algorithms; Text Compression: Shannon-Fano and Huffman codes, Arithmetic coding, Lempel-Ziv family of compression techniques, Burrows-Wheeler Transformation.