Learn · MIT OpenCourseWare

A picture of a blue frisbee with a four node graph printed on it.

Course6.046J / 18.410J34 lectures39 h 28 min

Design and Analysis of Algorithms

Prof. Erik Demaine, Prof. Srini Devadas and Prof. Nancy Lynch · Massachusetts Institute of Technology

Start with lecture 1 At MIT OpenCourseWare

About

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.

Lectures

Lecture Videos

  1. Lecture 1: Overview, Interval Scheduling 1 h 24 min · Video
  2. Lecture 2: Divide & Conquer: Convex Hull, Median Finding 1 h 21 min · Video
  3. Lecture 3: Divide & Conquer: FFT 1 h 21 min · Video
  4. Lecture 4: Divide & Conquer: van Emde Boas Trees 1 h 21 min · Video
  5. Lecture 5: Amortization: Amortized Analysis 1 h 16 min · Video
  6. Lecture 6: Randomization: Matrix Multiply, Quicksort 1 h 22 min · Video
  7. Lecture 7: Randomization: Skip Lists 1 h 21 min · Video
  8. Lecture 8: Randomization: Universal & Perfect Hashing 1 h 22 min · Video
  9. Lecture 9: Augmentation: Range Trees 1 h 25 min · Video
  10. Lecture 10: Dynamic Programming: Advanced DP 1 h 21 min · Video
  11. Lecture 11: Dynamic Programming: All-Pairs Shortest Paths 1 h 22 min · Video
  12. Lecture 12: Greedy Algorithms: Minimum Spanning Tree 1 h 23 min · Video
  13. Lecture 13: Incremental Improvement: Max Flow, Min Cut 1 h 23 min · Video
  14. Lecture 14: Incremental Improvement: Matching 1 h 23 min · Video
  15. Lecture 15: Linear Programming: LP, reductions, Simplex 1 h 23 min · Video
  16. Lecture 16: Complexity: P, NP, NP-completeness, Reductions 1 h 26 min · Video
  17. Lecture 17: Complexity: Approximation Algorithms 1 h 22 min · Video
  18. Lecture 18: Complexity: Fixed-Parameter Algorithms 1 h 18 min · Video
  19. Lecture 19: Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning Trees 1 h 18 min · Video
  20. Lecture 20: Asynchronous Distributed Algorithms: Shortest-Paths Spanning Trees 1 h 13 min · Video
  21. Lecture 21: Cryptography: Hash Functions 1 h 22 min · Video
  22. Lecture 22: Cryptography: Encryption 1 h 25 min · Video
  23. Lecture 23: Cache-Oblivious Algorithms: Medians & Matrices 1 h 21 min · Video
  24. Lecture 24: Cache-Oblivious Algorithms: Searching & Sorting 1 h 18 min · Video

Recitation Videos

  1. Recitation 1: Divide & Conquer: Smarter Interval Scheduling, Master Theorem, Strassen's Algorithm 54 min · Video
  2. Recitation 2: B-trees 31 min · Video
  3. Recitation 4: Randomization: Randomized Median 40 min · Video
  4. Recitation 5: Dynamic Programming: More Examples 53 min · Video
  5. Recitation 6: Greedy Algorithms: More Examples 23 min · Video
  6. Recitation 7: Incremental Improvement: Applications of Network Flow & Matching 52 min · Video
  7. Recitation 8: Complexity: More Reductions 46 min · Video
  8. Recitation 9: Complexity: Approximations 32 min · Video
  9. Recitation 10: More Distributed Algorithms 51 min · Video
  10. Recitation 11: Cryptography: More Primitives 50 min · Video

Syllabus and materials

At MIT OpenCourseWare, as the course publishes them.

Credits and licence

Institution
Massachusetts Institute of Technology
Department
Electrical Engineering and Computer Science; Mathematics
Taught by
Prof. Erik Demaine, Prof. Srini Devadas, Prof. Nancy Lynch
Term
Spring 2015
Level
Undergraduate
Language
English
Subjects
Mathematics, Computer science, Engineering
Source
MIT OpenCourseWare
Licence
CC BY-NC-SA 4.0, as MIT OpenCourseWare states it. Non-commercial use only. MIT OpenCourseWare's terms
Attribution
Prof. Erik Demaine, Prof. Srini Devadas, Prof. Nancy Lynch. Design and Analysis of Algorithms. Spring 2015. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu/. License: Creative Commons BY-NC-SA.
Who can watch
MIT OpenCourseWare gives no rating. Invisible Network shows it to Tweens profiles and older, judged from what the source says about it. How courses are placed