Shortest paths. Breadth-first search. Its properties. State graphs. Breadth-first search on 0-1 graphs. Graph of shortest paths. Relates problems.

SSSP. Non-negative weights. Dijkstra's algorithm. Negative weights. Bellman–Ford algorithm. SPFA. Negative Cycle Detection. All-pairs shortest path problem. Floyd–Warshall algorithm. Johnson's algorithm.

Segment trees. Top-down implementation. Bottom-up implementation. Segment trees applications. Persistent data structures. Persistent stack, persistent array. Persistent Fenwick and segment trees.

Algorithms for traversing a graph. DFS. Properties. DFS search tree. Edges classification. Linear bridge-finding algorithm. Linear articulation points finding algorithm. Strongly connected components. Tarjan's strongly connected components algorithm.

Minimum spanning trees. Tarjan's criterion. Kruskal's algorithm. Disjoin-Set-Union data structure, applications. Prim's algorithm.

Tree problems. Bottom-up approach. LCA problem. LCA algorithms.

Bipartite graphs. König’s criterion. Problems: maximum matching, minimum edge cover, maximum independent vertex set, minimum vertex cover. Connection of the problems. Berge's lemma. Kuhn algorithm. Kuhn algorithm properties. Minimal vertex cover by maximum matching. Cover DAG by minimal number of paths.

Graph flows. Flow networks. Max-flow min-cut theorem. Ford–Fulkerson algorithm. Edmonds–Karp algorithm. Problems on flows. Minimum-cost flow problem. Basic algorithm.

Introduction to strings. String searching (matching) problem. Pattern pre processings. Z-function, prefix-function. Their applications. Knuth–Morris–Pratt algorithm. Matching finite state machine.

Multiple pattern matching. Trie data structure. Aho-Corasick algorithm. Implementation details. Dynamic programming on a trie.
String hashing. Rabin-Karp algorithm. Fast substrings comparison with hashes.

Suffix array. LCP array.

Advanced Algorithms and Data Structures, Harbour.Space University: Introductory Contest.

SQRT decomposition. Description and motivation. Implementation of SQRT decomposition. Its applications: RMQ, RSQ and its variations. Queries decomposition.

Fenwick tree. Description and motivation. Implementation of Fenwick tree. Generalization for higher dimensions. Skip list data structure. Implementation details. Indexable skip list.

Heap data structure, heap properties and operations. HeapSort. Priority queue. Other heap applications. Mergeable heaps: binomial heap, pairing heap, randomized meldable heap.