Course on Efficient Algorithms by Alexander S. Kulikov. The course is taught at PDMI Computer Science Club. All slides and lecture notes are in Russian.
titleslideshandoutcontents
1. Approximation Algorithms. pdf pdf Approximation algorithms for vertex cover and set cover.
2. Approximation Algorithms. pdf pdf Approximation algorithm for shortest common superstring.
3. Approximation Algorithms. pdf pdf Approximation algorithm for metric TSP, FPTAS for knapsack.
4. Satisfiability. pdf pdf Reduction from Japanese puzzles and Eternity game to SAT and from MAX-CUT to MAX-SAT.
5. Algorithms for SAT. pdf pdf DPLL, PPSZ and random walk algorithms.
6. Approaches to Proving Upper Bounds for NP-hard Problems. pdf pdf Splitting, random evaluation order, local search, dynamic programming, reduction to easy problem, random reduction to easy problem, clever enumeration.
7. Linear Programming. pdf pdf Flows in networks, maximum bipartite matching, duality, simplex algorithm.
8. Approximation Algorithms. pdf pdf Approximation algorithms for weighted vertex cover and hitting set.
9. Randomized Algorithms. pdf pdf Randomized algorithms for verifying the correctness of matrix product, verifying the equivalence of long strings, zeroes of multivariate polynomials, verifying the equivalence of branching programs.
10. Randomized Algorithms. pdf pdf Randomized algorithm for minimum cut, randomized primality testing.
11. Randomized Algorithms. pdf pdf Randomized algorithms for all-pairs distances, Boolean matrix product witnesses, all-pairs shortest paths.
12. Online Algorithms. pdf pdf Online algorithms for paging and set cover.
13. Dynamic Programming. pdf pdf Edit distance, knapsack, chain matrix multiplication, shortest reliable paths, all-pairs shortest paths, TSP, independent sets in trees.
14. Greedy Algorithms. pdf pdf Activity-selection, Huffman encoding, set cover, vertex cover, SAT local search.
15. Maximum Matching. pdf pdf Augmenting paths, bipartite matching, general case.
16. Randomized Linear-time MST Algorithm. pdf pdf Randomized linear-time algorithm to find minimum spanning trees.
17. Polynomial Algorithm for LP. pdf pdf Karmarkar's polynomial algorithm for linear programming.
18. SDP-based Algorithms. pdf pdf Semidefinite programming, approximation algorithm for MAX-CUT, coloring a 3-colorable graph.
19. Derandomization. pdf pdf Method of conditional probabilities, method of small sample spaces.
20. Maximum Flow. Ford-Fulkerson method, preflow-push method, lift-to-front algorithm.
Sources: