Advanced Algorithms
Lecture notes and problem sets on advanced algorithms: network flows, linear programming, approximation, geometry and streaming.
Beyond the typical introductory course on algorithms lies a set of advanced topics, and this graduate course takes them up with a focus on design and correctness proofs. It covers data structures such as Fibonacci heaps and splay trees, network flows, linear programming and the ellipsoid algorithm. It then moves on to approximation algorithms for intractable problems, computational geometry and streaming algorithms for large data sets.
What You Will Achieve
- Analyze data structures such as Fibonacci heaps, splay trees and dynamic trees
- Design algorithms for maximum flow and minimum cost circulation
- Apply duality and the ellipsoid algorithm in linear programming
- Design and analyze approximation algorithms for intractable problems
Program Overview
Data Structures and Network Flows
Efficient structures and flow algorithms.
- Fibonacci heaps
- Splay trees and dynamic trees
- Maximum flow and minimum cost circulation
- Goldberg-Tarjan algorithm
Linear and Conic Programming
Structure, duality and algorithms.
- Duality, geometry and simplex
- The ellipsoid algorithm and its applications
- Conic programming
Approximation, Geometry and Large Data
Dealing with intractability and scale.
- Facility location and max-cut
- Multi-commodity flows and metric embeddings
- Convex hulls and Voronoi diagrams
- Streaming algorithms
Course Completion
Job Outlook
This material is designed for doctoral work in theoretical computer science, and it supports research on algorithm design and analysis.
Good for: Graduate students heading into theoretical computer science, and strong self-learners ready for a lot of correctness proofs.
Keep in mind: No textbook is required, so you rely on the lecture notes and references. Solutions are published for the 2001 problem sets, not the 2008 ones.
Bottom line: A rigorous survey of advanced algorithms, with problem sets from two terms to work through.
Frequently Asked Questions
Are solutions to the problem sets available?
For some. The assignments page lists six problem sets from 2008 without solutions, and six from 2001 with solutions, which suit self-checking.
Is there a required textbook?
No. Lecture notes are available for the term along with selected notes from a previous term, and reference textbooks for each topic are listed in the readings section.
How does the course handle large data sets?
Its last sessions cover streaming algorithms. The course outline also lists compression and compressed sensing under the heading of dealing with large data sets.



There are no reviews yet.