Graphs: basic notation, in-memory representation. Computing shortest paths with breadth first search. Depth first search and its basic properties.
Euler tours. Computing Euler tours with DFS. DFS tree and types of edges. Undirected graphs have no cross edges. Computing articulation points in linear time with DFS.
Bidirectional reachability. Strongly connected components. Graph condensation and its acyclicity. Computing strongly connected components via DFS. 1- and 2-cuts. Vector space spanned by graph edges and its dimension. Cycle subspace, its dimension and basis. Cut subspace. Orthogonal decomposition. Sampling elements in cycle space. Finding 2-cuts via randomized fingerprints.
Length functions and shortest paths. Distance labels and their relaxation. Ford--Bellman algorithm. Floyd algorithm. Dijkstra algorithm.
Complexity of Dijkstra algorithm. Power of data structures: binary heaps, k-ary heaps. Bidirected Dijkstra algorithm. Dual approach to shortest paths: potentials. Feasible potentials and conservative edge lengths. Johnson algorithm for computing all-pairs shortest paths for arbitrary edge lengths. Speeding up search with landmarks. ALT algorithm.
Minimum spanning tree problem. Good edge sets. Extending good edge sets by adding minimum cut edges. Kruskal algorithm, Prim algorithm, Boruvka algorithm and their complexities.
Minimum s-t cut and minimum global cut problems. Solving minimum global cut problem via a sequence of s-t problems. Contractions. Stoer-Wagner algorithm. Strings: basic notation and definitions. Substring matching problem. Naive algorithm. Borders and prefix function. Computing prefix function in linear time. Knuth-Morris-Pratt algorithm.
Z-function. Substring matching via Z-function. Constructing Z-function in linear time. Reducing space from O(P+T) to O(P). Computing 1-approximate substring matches via Z-function. Multiple pattern matching. Word trie: definition, in-memory representation and construction. Failure function. Aho-Corasick algorithm.
Matching with ?- and *-wildcards. Matching with *-wildcards via Aho-Corasick. Matching with ?-wildcards via convolutions. Reducing convolutions to polynomial multiplication. Further improvements: making alphabet binary, double cover trick.
FFT: definition and recursive implementation. Inverse FFT. Suffix trie and suffix tree. Space bounds. Explicit and implicit locations. Suffix links.
Outline of Ukkonen algorithm. Iterations and steps. Step types. Evolution of step types. Eliminating Type 1 steps via implicit labels at leaf edges. Eliminating Type 3 steps via early exit. Bounding the number of Type 2 steps. Finding locations for Type 2 steps via suffix links. Skip-count trick for computing suffix links. Following a suffix link does not decrease the current depth by most than 1. Bounding the running time of Ukkonen algorithm. Suffix arrays. Finding substring matches via suffix array and binary search. Karp-Miller-Rosenberg labeling algorithm for computing suffix arrays in O(n log n) time.
Speeding up substring matching with LCP values. Karkainen-Sanders algorithm for linear-time suffix array construction. LCAs in suffix tree are related to LCPs. LCP array: definition and basic properties. Computing LCP array from suffix array in linear time (Arikawa-Arimura-Lee-Kasai-Park algorithm).
Solving longest common substring problem via suffix trees and suffix arrays. Approximate substring matching with edit distance. Alignment graph and dynamic programming approach. Landau-Vishkin algorithm. Reachable sets and their boundaries. Initializing and updating boundary set. LCPs to the rescue.