Instructor:
Semester:
- 2013 Autumn/Monsoon (Aug - Dec)
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.