6.854
Advanced Algorithms
Fall 2008
Topics
- Fibonacci heaps
- Network flows
- Maximum flow; minimum cost circulation
- Goldberg-Tarjan min-cost circulation algorithm
- Cancel-and-tighten algorithm; binary search trees
- Splay trees
- Dynamic trees (part 1)
- Dynamic trees (part 2)
- Linear programming (LP)
- LP: duality, geometry, simplex
- LP: complexity; introduction to the ellipsoid algorithm
- LP: ellipsoid algorithm
- LP: applications of the ellipsoid algorithm
- Conic programming I
- Conic programming II
- Approximation algorithms
- Approximation algorithms (facility location)
- Approximation algorithms (max-cut)
- Max-cut and sparsest-cut
- Multi-commodity flows and metric embeddings
- Convex hulls
- Convex hulls and fixed dimension LP
- Voronoi diagrams
- Approximation scheme for the Euclidean traveling salesman problem
- Streaming algorithms
- Streaming algorithms (cont’d)
Readings
- TOPICS: Network flows · READINGS: Ahuja, R. K., T. L. Magnanti, and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications . Upper Saddle River, NJ: Prentice Hall, 1993. ISBN: 9780136175490.
- Schrijver, A. Theory of Linear and Integer Programming . New York, NY: John Wiley & Sons, 1998. ISBN: 9780471982326.
- Groetschel, M., L. Lovasz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization . New York, NY: Springer-Verlag, 1993, chapter 3. ISBN: 9780387567402. [The standard reference on the ellipsoid. The most complete and precise description.]
- Chvatal, V. Linear Programming . New York, NY: W.H. Freeman and Company, 1983, appendix. ISBN: 9780716715870. [An easy to read description without all the details.]
- Korte, B. H., and J. Vygen. Combinatorial Optimization . New York, NY: Springer-Verlag, 2002, chapter 4. ISBN: 9783540431541. [A detailed description.]
- Roos, C., T. Terlaky, and J.-Ph. Vial. Theory and Algorithms for Linear Optimization: An Interior Point Approach . New York, NY: John Wiley & Sons, 1997. ISBN: 9780471956761.
- Boyd, Stephen, and Lieven Vandenberghe. Convex Optimization . Cambridge, UK: Cambridge Univ. Press, 2005. ISBN: 9780521833783
- Vazirani, V. Approximation Algorithms . New York, NY: Springer-Verlag, 2004. ISBN: 9783540653677.
- Hochbaum, D., ed. Approximation Algorithms for NP-Hard Problems . Boston: PWS Publishing Company, 1996. ISBN: 9780534949686.
- de Berg, Mark, O. Cheong, M. van Kreveld, and M. Overmars. Computational Geometry. 3rd ed. New York, NY: Springer-Verlag, 2008. ISBN: 9783540779735
- S. Muthukrishnan, “Data streams: Algorithms and applications”, Foundations and Trends in Theoretical Computer Science, Volume 1, issue 2, 2005.
- Lov’asz, L. “An Algorithmic Theory of Numbers, Graphs, and Convexity.” In CBMS Regional Conference Series in Applied Mathematics (SIAM, 1986) . Philadelphia, PA: Society for Industrial and Applied Mathematics, 1987. ISBN: 9780898712032.
Fall 2005
Topics
- Course Introduction Fibonacci Heaps
- MST Persistent Data Structures
- Splay Trees
- Splay Trees (cont.) Suffix Trees Tries
- Suffix Trees (cont.) Tries (cont.) Dial’s Algorithm
- Dijkstra’s Algorithm Van Emde Boas Queues
- Van Emde Boas Queues (cont.) Hashing
- 2-Level Hashing Network Flows
- Network Flows: Augmenting Paths, Maximum Augmenting Paths, Scaling
- Reductions between Flow Problems Bipartite Matching Shortest Augmenting Path Blocking Flows
- Blocking Flows (cont.)
- Min-Cost Flows
- Min-Cost Flows (cont.) Linear Programming
- Linear Programming (cont.) Structure of Optima Weak Duality
- Linear Programming (cont.) Strong Duality
- Linear Programming (cont.) Complementary Slackness Algorithms: Simplex, Ellipsoid
- Linear Programming (cont.) Algorithms: Interior Point NP-hard problems
- Approximation Algorithms
- 4/3-Approximation for TSP
- Relaxations Directed TSP
- Randomized Rounding Chernoff Bound Fixed Parameter Tractability Kernelization
- Online Algorithms (Ski Rental, Load Balancing, Paging)
- Randomized Online Algorithms (Adversaries, Fiat’s Marking Algorithm, Potential Functions, Yao’s Minimax Principle)
- K-Server Problem Double-Coverage Algorithm Computational Geometry Introduction (Orthogonal Range Search)
- Sweep Algorithms (Convex Hull, Segment Intersection, Voronoi Diagrams)
- Sweep Algorithms (Voronoi Diagrams) Randomized Incremental Constructions Backwards Analysis Linear Programming in Fixed Dimension
- (Optional Material) External Memory Algorithms
- (Optional Material) Cache Oblivious Algorithms: Matrix Multiplication, Linked Lists, Median
- (Optional Material) Cache Oblivious Algorithms: Search Streaming Model
Readings
- Ahuja, Magnanti, and Orlin. Network Flows . Upper Saddle River, NJ: Prentice Hall, 1993. ISBN: 013617549X.
- Motwani and Raghavan. Randomized Algorithms . Cambridge, UK: Cambridge University Press, 1995. ISBN: 0521474655.
- Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology . Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198.
- Borodin, Allan, and Ran El-Yaniv. Online Computation and Competitive Analysis . Cambridge, UK: Cambridge University Press, 1998. ISBN: 0521563925.
- Tarjan, Robert. Data Structures and Network Algorithms . Philadelphia, PA: Society for Industrial and Applied Mathematics, 1983. ISBN: 0898711878. A classic - no longer up to date, but outstanding writing.
- Berg, Mark de, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications . New York, NY: Springer-Verlag, 2000. ISBN: 3540656200.
- Hochbaum, Dorit, ed. Approximation Algorithms for NP-Hard Problems . Boston, MA: PWS Publishing Company, 1997. ISBN: 0534949681.
Sources
- Course catalogue ↗Historical OpenCourseWare
- MIT OpenCourseWare ↗Fall 2008
- MIT OCW readings ↗
- MIT OCW calendar ↗
- MIT OCW syllabus ↗
- MIT OCW readings ↗
- MIT OCW syllabus ↗
- MIT OCW calendar ↗
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.
- Historical MIT OpenCourseWare offering. Named reading entries and schedule topics are automatically extracted from the linked source pages.