Course Syllabus:

-- Max-flow and related topics: Ford-Fulkerson algorithm, Max flow-min cut theorem, Maximum matching in bipartite graphs, proof of Hall's theorem, Dinic's algorithm, Preflow-Push algorithms

-- Randomized algorithms: randomized quicksort, randomized min-cut algorithm, Miller-Rabin primality testing

-- Shortest path and MST algorithms, supporting data structures: Bellman-Ford algorithm, Dijkstra's algorithm, Fibonacci Heaps, Prim's algorithm, Kruskal's algorithm, Union-Find data structure

-- Other topics: Polynomials and the FFT, String Matching with finite automaton, Knuth-Morris-Pratt algorithm, randomized incremental algorithms for some geometric problems (2-D convex hull, 2-D linear programming etc.)

-- NP-hardness and approximation algorithms: SAT and examples of other NP-complete problems, pseudopolynomial time algorithm for the knapsack problem, approximation algorithms for vertex cover, metric TSP, introduction to linear programming.

-- Online algorithms (if there is time)

---------------------------------------------------------------

Reading material: Lecture notes from the net and topics from "Randomized Algorithms" by Motwani and Raghavan.