Algorithms and data structures. Part 2.

Lecture 1. Breadth first search. Depth first search (part 1)

Graphs: basic notation, in-memory representation. Computing shortest paths with breadth first search. Depth first search and its basic properties.

Lecture 2. Depth first search (part 2)

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.

Lecture 3. Depth first search (part 3)

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.

Lecture 4. Shortest paths (part 1)

Length functions and shortest paths. Distance labels and their relaxation. Ford--Bellman algorithm. Floyd algorithm. Dijkstra algorithm.

Lecture 5. Shortest paths (part 2)

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.

Lecture 6. Minimum spanning trees

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.

Lecture 7. Minimum cuts. Substring matching (part 1)

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.

Lecture 8. Substring matching (part 2)

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.

Lecture 9. Substring matching (part 3)

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.

Lecture 10. Substring matching (part 4). Suffix trees (part 1)

FFT: definition and recursive implementation. Inverse FFT. Suffix trie and suffix tree. Space bounds. Explicit and implicit locations. Suffix links.

Lecture 11. Suffix trees (part 2). Suffix arrays (part 1)

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.

Lecture 12. Suffix arrays (part 2).

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).

Lecture 13. Longest common substrings. Approximate substring matching.

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.