Design and Analysis of Algorithms

Course Description

This is an intermediate algorithms course with an emphasis on teaching techniques for the design and analysis of efficient algorithms, emphasizing methods of application. Topics include divide-and-conquer, randomization, dynamic programming, greedy algorithms, incremental improvement, complexity, and cryptography.

This course is taught by Prof. Erik Demaine, Prof. Srinivas Devadas, and Prof. Nancy Lynch.

Copyright Information

Erik Demaine, Srinivas Devadas, and Nancy Lynch. 6.046J Design and Analysis of Algorithms, Spring 2015. (Massachusetts Institute of Technology: MIT OpenCourseWare), (Accessed 3 Apr, 2016). License: Creative Commons BY-NC-SA
Design and Analysis of Algorithms
Frisbees® featuring a flow network were tossed out during lectures to reward class participation. (Photo courtesy of Prof. Devadas)
Not yet rated

Video Lectures & Study Materials

Visit the official course website for more study materials:

# Lecture Play Lecture
1 Course Overview, Interval Scheduling Play Video
2 Divide & Conquer: Convex Hull, Median Finding Play Video
3 Recitation 1: Matrix Multiplication and the Master Theorem Play Video
4 Divide & Conquer: FFT Play Video
5 Recitation 2: 2-3 Trees and B-Trees Play Video
6 Divide & Conquer: van Emde Boas Trees Play Video
7 Amortization: Amortized Analysis Play Video
8 Randomization: Matrix Multiply, Quicksort Play Video
9 Recitation 4: Randomized Select and Randomized Quicksort Play Video
10 Randomization: Skip Lists Play Video
11 Randomization: Universal & Perfect Hashing Play Video
12 Recitation 5: Dynamic Programming Play Video
13 Augmentation: Range Trees Play Video
14 Dynamic Programming: Advanced DP Play Video
15 Dynamic Programming: All-Pairs Shortest Paths Play Video
16 Greedy Algorithms: Minimum Spanning Tree Play Video
17 Recitation 6: Greedy Algorithms Play Video
18 Incremental Improvement: Max Flow, Min Cut Play Video
19 Incremental Improvement: Matching Play Video
20 Recitation 7: Network Flow and Matching Play Video
21 Linear Programming: LP, reductions, Simplex Play Video
22 Complexity: P, NP, NP-completeness, Reductions Play Video
23 Recitation 8: NP-Complete Problems Play Video
24 Complexity: Approximation Algorithms Play Video
25 Complexity: Fixed-Parameter Algorithms Play Video
26 Recitation 9: Approximation Algorithms: Traveling Salesman Problem Play Video
27 Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees Play Video
28 Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees Play Video
29 Recitation 10: Distributed Algorithms Play Video
30 Cryptography: Hash Functions Play Video
31 Cryptography: Encryption Play Video
32 Recitation 11: Cryptography: More Primitives Play Video
33 Cache-Oblivious Algorithms: Medians & Matrices Play Video
34 Cache-Oblivious Algorithms: Searching & Sorting Play Video


There are no comments. Be the first to post one.
  Post comment as a guest user.
Click to login or register:
Your name:
Your email:
(will not appear)
Your comment:
(max. 1000 characters)
Are you human? (Sorry)
CosmoLearning is promoting these materials solely for nonprofit educational purposes, and to recognize contributions made by Massachusetts Institute of Technology (MIT) to online education. We do not host or upload any copyrighted materials, including videos hosted on video websites like YouTube*, unless with explicit permission from the author(s). All intellectual property rights are reserved to MIT and involved parties. CosmoLearning is not endorsed by MIT, and we are not affiliated with them, unless otherwise specified. Any questions, claims or concerns regarding this content should be directed to their creator(s).

*If any embedded videos constitute copyright infringement, we strictly recommend contacting the website hosts directly to have such videos taken down. In such an event, these videos will no longer be playable on CosmoLearning or other websites.