Advanced Algorithms Course at MIT
Here is the first of four posts I will do from the best of
MIT's open-content computer science courses. This one is called 'Advanced
Algorithms', and if you need to learn more about
algorithms and what they can do for you, these learning materials will
help you out.
This course is a first-year graduate course in algorithms. Emphasis is placed on fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms, network optimization, parallel algorithms, computational geometry, online algorithms, external memory, cache, and streaming algorithms, and data structures.
Advanced
Algorithms Course at MIT
Lecture notes from the 2004 version of this course.
Related Posts:
Free Algorithms Training Course Global Optimization Algorithms eBook Free Algorithms Book 32-lesson C++ Programming Tutorial and Examples Algorithms Online Book and Course Lecture Slides
This course is a first-year graduate course in algorithms. Emphasis is placed on fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms, network optimization, parallel algorithms, computational geometry, online algorithms, external memory, cache, and streaming algorithms, and data structures.
Advanced
Algorithms Course at MIT
Lecture Notes
Although some of the lecture below were scribed during the 2005 version of this course, many of the scribed notes below are from previous versions of the course. These older notes were made available to the students. Scribed notes were taken by the students and used with permission. The instructor notes often span several lectures| Lec | Topics | Scribe Notes | Instructor Notes |
|---|---|---|---|
| 1 | Course Introduction Fibonacci Heaps |
Fibonacci Heaps (PDF) (Courtesy of David Andersen, Ioana Dumitriu, John Dunagan, and Akshay Patil.) | (PDF
1) (PDF 2) |
| 2 |
MST Persistent Data Structures |
Persistent Data Structures (PDF) (Courtesy of Sommer Gentry and Eddie Kohler.) | (PDF) |
| 3 | Splay Trees | Splay Trees (PDF) (Courtesy of Xin Zhang.) | (PDF) |
| 4 |
Splay Trees (cont.) Suffix Trees Tries |
Suffix Trees and Fibonacci Heaps (PDF) | (PDF) |
| 5 |
Suffix Trees (cont.) Tries (cont.) Dial's Algorithm |
||
| 6 |
Dijkstra's Algorithm Van Emde Boas Queues |
Van Emde Boas Queues (PDF) (Courtesy of Abhi Shelat, Andrew Menard, and Akshay Patil.) | (PDF) |
| 7 |
Van Emde Boas Queues (cont.) Hashing |
(PDF) | |
| 8 |
2-Level Hashing Network Flows |
Maximum Flows (PDF) (Courtesy of Alexandr Andoni.) | (PDF) |
| 9 |
Network Flows: Augmenting Paths,
Maximum Augmenting Paths, Scaling |
||
| 10 |
Reductions between Flow Problems Bipartite Matching Shortest Augmenting Path Blocking Flows |
||
| 11 |
Blocking Flows (cont.) |
||
| 12 |
Min-Cost Flows |
Min-Cost Flow Algorithms (PDF) (Courtesy of Wendy Chang.) | (PDF) |
| 13 | Min-Cost Flows (cont.) Linear Programming |
(PDF) | |
| 14 |
Linear Programming (cont.) Structure of Optima Weak Duality |
Duality (PDF) (Courtesy of Jay-Kumar Sundararajan.) | |
| 15 | Linear Programming (cont.) Strong Duality |
Duality(PDF) (Courtesy of Jay-Kumar Sundararajan.) | |
| 16 |
Linear Programming (cont.) Complementary Slackness Algorithms: Simplex, Ellipsoid |
Duality (PDF) (Courtesy of Jay-Kumar Sundararajan.) | |
| 17 |
Linear Programming (cont.) Algorithms: Interior Point |
||
| 18 |
Approximation Algorithms NP-hard problems |
(PDF) | |
| 19 | 4/3-Approximation for TSP |
||
| 20 |
Relaxations Directed TSP |
||
| 21 |
Randomized Rounding Chernoff Bound Fixed Parameter Tractability Kernelization |
(PDF) | |
| 22 | Online Algorithms (Ski Rental, Load Balancing, Paging) | Lower Bounds for Competitive
Ratios of Randomized Online Algorithms (PDF) (Courtesy of Chun-Chieh Lin.) |
(PDF) |
| 23 | Randomized Online Algorithms
(Adversaries, Fiat's Marking Algorithm, Potential Functions, Yao's
Minimax Principle) |
Lower Bounds for Competitive
Ratios of Randomized Online Algorithms (PDF) (Courtesy of Chun-Chieh Lin.) |
|
| 24 |
K-Server Problem Double-Coverage Algorithm Computational Geometry Introduction (Orthogonal Range Search) |
||
| 25 | Sweep Algorithms (Convex Hull,
Segment Intersection, Voronoi Diagrams) |
Sweep Line (PDF) (Courtesy of Matt Rasmussen.) | (PDF) |
| 26 |
Sweep Algorithms (Voronoi
Diagrams) Randomized Incremental Constructions Backwards Analysis Linear Programming in Fixed Dimension |
||
| 27 | (Optional Material) External
Memory Algorithms |
(PDF) | |
| 28 |
(Optional Material) Cache
Oblivious Algorithms: Matrix Multiplication, Linked Lists, Median |
||
| 29 |
(Optional Material) Cache Oblivious Algorithms: Search Streaming Model |
||
| 29 | (Optional Material) Parallel Algorithms | (PDF) |
Lecture notes from the 2004 version of this course.
| Lec | Topics | Scribe Notes |
|---|---|---|
| 1 | Course Introduction Fibonacci Heaps |
(PDF) Courtesy of David Andersen, Ioana Dumitriu, John Dunagan, and Akshay Patil.) |
| 2 | Persistent Data Structures Suffix Trees |
(PDF
1) (Courtesy of Sommer Gentry and Eddie Kohler.) (PDF 2) (Courtesy of Jiawen Chen.) |
| 3 | Suffix Trees (cont.) | (PDF) |
| 4 | Treaps | |
| Splay
Trees |
(PDF) (Courtesy of Naveen Sunkavally.) | |
| 5 | Hashing: 2-Universal, Perfect Hashing Fingerprinting |
|
| 6 | Fingerprinting (cont.) Max Flows |
(PDF
1) (Courtesy of Jiawen Chen.) (PDF 2) (Courtesy of Alexandr Andoni.) |
| 10 | Min Cost Flow Algorithms Linear Programming |
(PDF 1) (Courtesy of Brian Dean and John Jannotti.) |
| 11 | Goldberg-Tarjan Min-cost Flow | (PDF) (Courtesy of Mohammad Hajiaghayi and Vahab Mirrokni.) |
| 14 |
LP: Interior Points Algorithm Approximation Algorithms: Constant, Relative Approximation |
(PDF) (Courtesy of Jason Eisenberg.) |
| 16 | Approximation Algorithm: Rounding, Relaxation | (PDF) (Courtesy of Sachin Katti.) |
| 17 | Approximation Algorithm: LP Relaxation, Randomized Rounding | (PDF) (Courtesy of Shannon McDonald.) |
| 18 |
Fixed Parameter Tractability |
(PDF) (Courtesy of Shannon McDonald.) |
| 22 |
Lower Bounds for Randomized Online Algorithms Geometry: Range Search |
(PDF) (Courtesy of Nick Harvey.) |
Readings
The
following papers
are related to the second lecture:
Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press, 2001. ISBN: 0262032937.
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.
Popularity: 14% [?]
Related Posts: