everything.study
18.415

Advanced Algorithms

5-0-10 units · Graduate

See description under subject 6.5210J.

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

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

  • Buy at MIT Press Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms . 2nd ed. Cambridge, MA: MIT Press , 2001. ISBN: 0262032937. ↗
    Listed reading
  • Ahuja, Magnanti, and Orlin. Network Flows . Upper Saddle River, NJ: Prentice Hall, 1993. ISBN: 013617549X.
    Listed reading
  • Motwani and Raghavan. Randomized Algorithms . Cambridge, UK: Cambridge University Press, 1995. ISBN: 0521474655.
    Listed reading
  • Gusfield, Dan. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology . Cambridge, UK: Cambridge University Press, 1997. ISBN: 0521585198.
    Listed reading
  • Borodin, Allan, and Ran El-Yaniv. Online Computation and Competitive Analysis . Cambridge, UK: Cambridge University Press, 1998. ISBN: 0521563925.
    Listed reading
  • 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.
    Listed reading
  • Berg, Mark de, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry: Algorithms and Applications . New York, NY: Springer-Verlag, 2000. ISBN: 3540656200.
    Listed reading
  • Hochbaum, Dorit, ed. Approximation Algorithms for NP-Hard Problems . Boston, MA: PWS Publishing Company, 1997. ISBN: 0534949681.
    Listed reading

Prerequisites & course information

Same subject as 6.5210J Prereq: 6.1220[J] and ( 6.1200[J] , 6.3700 , or 18.600 ) G (Fall) 5-0-10 units

Sources