Design and Analysis of Algorithms
Intermediate algorithms: divide and conquer, randomization, dynamic programming, greedy, network flow, NP-completeness, approximation and cryptography.
Designing an efficient algorithm takes a toolkit of techniques and the means to prove how well they perform. This intermediate algorithms course teaches both, emphasizing how to apply them, in recorded lectures with notes and recitation videos: divide and conquer, amortization, randomization, dynamic programming, greedy algorithms, network flow and matching, linear programming, complexity and approximation, distributed algorithms, cryptography and cache-oblivious algorithms.
What You Will Achieve
- Design algorithms with divide and conquer, dynamic programming, greedy and randomized techniques
- Analyze running times, including amortized and expected costs
- Model problems as network flow, matching or linear programs
- Prove problems NP-complete and design approximation and fixed-parameter algorithms
Program Overview
Core Design Techniques
The main strategies for building efficient algorithms.
- Divide and conquer: convex hull, median finding, FFT and van Emde Boas trees
- Amortized analysis and union-find
- Randomization: quicksort, skip lists and universal and perfect hashing
- Dynamic programming, all-pairs shortest paths and greedy minimum spanning trees
Flows, Optimization and Complexity
Network flow, linear programming and hard problems.
- Max flow, min cut and matching
- Linear programming, reductions and the simplex method
- P, NP, NP-completeness and reductions
- Approximation and fixed-parameter algorithms
Advanced Topics
Algorithms for distributed systems, security and memory.
- Synchronous and asynchronous distributed algorithms
- Cryptography: hash functions, encryption and other primitives
- Cache-oblivious algorithms for medians, matrices, searching and sorting
Course Completion
Job Outlook
Algorithm design is used in software engineering, competitive programming, systems and infrastructure, operations research and theoretical computer science research.
Good for: Learners who want a wide toolkit of algorithm design techniques, with the proofs and analysis behind each one.
Keep in mind: The problem sets draw on Introduction to Algorithms by Cormen, Leiserson and colleagues, third edition, so you will want access to that textbook.
Bottom line: A complete intermediate algorithms course with solutions for every problem set and exam.
Frequently Asked Questions
Are solutions published?
Yes. Solutions are published for all ten problem sets, both quizzes and the final exam.
How should an algorithm be written up?
As a short essay: a description in English with pseudocode if helpful, a worked example or diagram, a proof of correctness and an analysis of running time, with clarity valued as much as correctness.
Who teaches the lectures?
Erik Demaine, Srini Devadas and Nancy Lynch taught this spring 2015 version, and the site includes their notes and recitation videos.



There are no reviews yet.