Links
Course overview
Fundamental techniques for designing efficient algorithms, proving their correctness, and analyzing their running time.
Main topics
- asymptotic analysis, summations, recurrence relations
- stable matching: Gale-Shapley, male optimality, properties
- graphs: representation, BFS, bipartiteness, DFS, edge classification,connectivity, topological sorting, biconnected components
- greedy algorithms: interval scheduling, interval partitioning, minimizing lateness, shortest paths, minimum spanning trees, center selection
- dynamic programming: weighted interval scheduling, segmented least squares, knapsack, sequence alignment, sequence alignment in linear space, shortest paths with negative weights (Bellman-Ford), matrix chain multiplication
- network flow: Ford-Fulkerson, residual network, max-flow min-cut, bipartite matching, Edmonds-Karp, bipartite matching, edge disjoint paths, network connectivity, circulation with demands, circulation with demands and lower bounds
- complexity theory: reductions, NP-completeness, complexity classes, approximation algorithms for NP-hard problems