Advanced Algorithms

View Course Materials

Buying via our links supports this free directory · Affiliate disclosure.
Course facts
  • Payment: Free, no certificate
  • Credits: Non Credit
  • Learning style: Self-paced, start anytime
  • Resources: Lecture Notes; Problem Set Solutions; Problem Sets
MIT OpenCourseWare details
  • As taught in: Fall 2008
  • Department: Electrical Engineering and Computer Science, Mathematics
Created byMIT
Available onMIT OpenCourseWareMIT OpenCourseWare

Course Details
Learning Style

Start Anytime

Level

All Levels

Study Mode

100% Online

Outcomes
Academic Credits

Non Credit

Price & Terms
Pricing Model

Free Content (No Certificate)

Technical
Content Medium

Text Based

Specification
Access

Free Access

Academic Level

Graduate

SKU: advanced-algorithms-mitocw Category: Brand:

Lecture notes and problem sets on advanced algorithms: network flows, linear programming, approximation, geometry and streaming.

At a glance
LevelAll Levels
AccessFree access
FormatText Based
As taught inFall 2008
DepartmentElectrical Engineering and Computer Science, Mathematics
Add your review
Add to wishlistAdded to wishlistRemoved from wishlist 0
Add to compare

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.


Before you start: Prerequisites include “Introduction to algorithms” (at the level of 18.410J / 6.046J), linear algebra (at the level of 18.06 or 18.700), and mathematical maturity (since we’ll be doing a lot of correctness proofs). The course is especially designed for doctoral students interested in theoretical computer science.

Our take

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.

User Reviews

0.0 out of 5
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0
★★★★★
0

No reviews yet. Be the first to review this course.

There are no reviews yet.

Write your review

Reviews can only be posted by registered learners. Log in, then you will return here to post.

×

    Report this page
    LiveTalent
    Logo
    Compare items
    • Total (0)
    Compare
    0