Co bylo

Text Algorithms 2019/20

   Summary of Lectures

Lecture 1
Informal discussion about the cirriculum
 (pattern matching; special families of words; non-standard stringology)
Weak and strong periodicity lemma with proofs
 (Euclid's algorithm for the weak version; graph-theoretical interpretation for the strong version)
Primitive words, synchronization property
Computation of the border array

Lecture 2
Morris-Pratt (MP) algorithm
Computation of covers, Breslauer's algorithm
Knuth-Morris-Pratt (KMP) algorithm
Real-time MP (O(1) delay)
Frugal MP (3/2 n comparisons)
Materials: MP and KMP: in Polish, in English. Covers: in English.

Lecture 3
Computation of PREF table
Computation of covers by Moore and Smyth's algorithm
Boyer-Moore (BM) algorithm
Computation of BMShift array
A part of the proof that BM algorithm makes <= 4n comparisons
Materials: BM and PREF: in Polish, in English. Covers: in English.

Lecture 4
Completing the proof that BM algorithm makes <= 4n comparisons
BM automata, lower bound Omega(m3)
MP algorithm for parameterized and order-preserving models
Introduction to suffix trees
Materials: op-model: problem "Matching", in English, BM automata: in Polish.

Lecture 5
O(n*maxdepth)-time simpler version of McCreight's algorithm
McCreight's algorithm for suffix tree construction
Ukkonen's algorithm for suffix tree construction
Materials: in Polish.

Lecture 6
O(1)-time RMQ and LCA queries after O(n) time and space preprocessing
O(1)-time LCP queries
Kangaroo jumps
Circular Pattern Matching with k mismatches in O(nk) time
longest common factor of n strings of total length O(n) in O(n) time
Materials: slides, Circular (sect. 2 and 3), LCF of many strings.

Lecture 7
KMR - Dictionary of Basic Factors
Suffix Array (SA), examples for Thue-Morse and Fibonacci words
Karkkainen and Sanders (KS) algorithm for constructing the SA
Constructing the suffix tree from the suffix array
Arrays RANK and LCP
Materials: In English: slides - KS algorithm, DBF - Section 2, LCP array paper. In Polish: smurf
Lecture 8
Pattern matching using SA and O(1)-time lcp queries in O(|pattern| + log |text|) time
Computation of seeds, part I: computation of quasiseeds and right candidates;
  Joinable Segment Trees
Materials: In English: a paper: a harder O(n)-time algorithm for seeds,
a paper: JSTs for O(n log n)-time seeds computation.
Lecture 9
Computation of seeds, part II: left candidates (sketch), combine,
   Weighted Ancestor Queries in O(log n) time after O(n)-time preprocessing via HLD
Computation of primitively rooted squares in O(n log n) time using
   Gusfield's and Stoye's algorithm (1998),
   part I: examples and branching occurrences of squares
Lecture 10
Computation of primitively rooted squares in O(n log n) time using
   Gusfield's and Stoye's algorithm (1998),
   part II: main algorithm and a combinatorial proof
An infinite family of strings of length n that contain n-o(n) different squares
A proof that a string of length n has at most 2n different squares
Materials:  O(n log n) time algorithm and bound for p-squares,
example of strings rich in powers, proof of the 2n bound.
Lecture 11
Runs, proof of "Runs" theorem
Lyndon words and their properties
Computing all runs in a string in linear time
Materials:  runs
Lecture 12
Computing all distinct squares from runs in linear time
Runs in Sturmian words
Materials:  squares (paper), runs in Sturmian words (paper)
Lecture 13
Karp-Rabin hashing
Streaming pattern matching
Materials:  presentation
Problems from Tutorials
How many binary words of length p+q-2 and having periods p and q
Shortest periods of prefixes of a Fibonacci string
Greatest fixed-density necklaces (see paper)
Discussions on Real-time and Frugal MP
Periodicity lemma for partial words with one hole (see paper)
Computing PREF table from border table and converse (paper)
Galil's improvement to BM algorithm (see book)
An example that BM algorithm can make approx. 3n comparisons
An algorithm that computes the position of the kth letter a in Fibonacci word in O(log n) time
Fibonacci words and Wythoff's game (see paper)
Thue-Morse words and Tarry-Escott problem (see wiki)
Suffix tree of Fib'n (see smurf)
Applications of suffix tree: counting all distinct factors of each length; counting distinct factors with an occurrence that avoids a given position and factors with an occurrence that contains a given position
Computing the i-th digit and the number of ones in n-th Pascal word; self-reproducing words
SA of Thue-Morse
Comparing suffixes of Fib'i strings
Shortest covers of cyclic shifts of Fibonacci strings
Computing the shortest covers of all cyclic shifts of a string in O(n log n) time and the shortest among them in O(n) time
Number of square factors in labeled trees
Computing the number of different square factors in combs (special labeled trees)
The maximum number of cubes in a string of length n is n-2
Combinatorics of Lyndon words (in Polish)
Infinite square-free words, relation to Thue-Morse words
Winning strategies for a two-player avoiding squares game (over 9-letter alphabet) and avoiding overlaps game (over 4-letter alphabet)