WithTranscript.ai
...

MIT OpenCourseWare · series 3 of 10

6.046J Design and Analysis of Algorithms

Erik Demaine, Srini Devadas and Nancy Lynch: divide and conquer, randomization, flows, linear programming, NP-completeness, distributed algorithms and cryptography. Spring 2015.

34 lectures0 min

Episodes

  1. Lec 1

    Course Overview, Interval SchedulingNot yet

    Watch on YouTube ↗
  2. Lec 2

    Divide & Conquer: Convex Hull, Median FindingNot yet

    Watch on YouTube ↗
  3. R1

    Matrix Multiplication and the Master TheoremNot yet

    Watch on YouTube ↗
  4. Lec 3

    Divide & Conquer: FFTNot yet

    Watch on YouTube ↗
  5. R2

    2-3 Trees and B-TreesNot yet

    Watch on YouTube ↗
  6. Lec 4

    Divide & Conquer: van Emde Boas TreesNot yet

    Watch on YouTube ↗
  7. Lec 5

    Amortization: Amortized AnalysisNot yet

    Watch on YouTube ↗
  8. Lec 6

    Randomization: Matrix Multiply, QuicksortNot yet

    Watch on YouTube ↗
  9. R4

    Randomized Select and Randomized QuicksortNot yet

    Watch on YouTube ↗
  10. Lec 7

    Randomization: Skip ListsNot yet

    Watch on YouTube ↗
  11. Lec 8

    Randomization: Universal & Perfect HashingNot yet

    Watch on YouTube ↗
  12. R5

    Dynamic ProgrammingNot yet

    Watch on YouTube ↗
  13. Lec 9

    Augmentation: Range TreesNot yet

    Watch on YouTube ↗
  14. Lec 10

    Dynamic Programming: Advanced DPNot yet

    Watch on YouTube ↗
  15. Lec 11

    Dynamic Programming: All-Pairs Shortest PathsNot yet

    Watch on YouTube ↗
  16. Lec 12

    Greedy Algorithms: Minimum Spanning TreeNot yet

    Watch on YouTube ↗
  17. R6

    Greedy AlgorithmsNot yet

    Watch on YouTube ↗
  18. Lec 13

    Incremental Improvement: Max Flow, Min CutNot yet

    Watch on YouTube ↗
  19. Lec 14

    Incremental Improvement: MatchingNot yet

    Watch on YouTube ↗
  20. R7

    Network Flow and MatchingNot yet

    Watch on YouTube ↗
  21. Lec 15

    Linear Programming: LP, reductions, SimplexNot yet

    Watch on YouTube ↗
  22. Lec 16

    Complexity: P, NP, NP-completeness, ReductionsNot yet

    Watch on YouTube ↗
  23. R8

    NP-Complete ProblemsNot yet

    Watch on YouTube ↗
  24. Lec 17

    Complexity: Approximation AlgorithmsNot yet

    Watch on YouTube ↗
  25. Lec 18

    Complexity: Fixed-Parameter AlgorithmsNot yet

    Watch on YouTube ↗
  26. R9

    Approximation Algorithms: Traveling Salesman ProblemNot yet

    Watch on YouTube ↗
  27. Lec 19

    Synchronous Distributed Algorithms: Symmetry-Breaking. Shortest-Paths Spanning TreesNot yet

    Watch on YouTube ↗
  28. Lec 20

    Asynchronous Distributed Algorithms: Shortest-Paths Spanning TreesNot yet

    Watch on YouTube ↗
  29. R10

    Distributed AlgorithmsNot yet

    Watch on YouTube ↗
  30. Lec 21

    Cryptography: Hash FunctionsNot yet

    Watch on YouTube ↗
  31. Lec 22

    Cryptography: EncryptionNot yet

    Watch on YouTube ↗
  32. R11

    Cryptography: More PrimitivesNot yet

    Watch on YouTube ↗
  33. Lec 23

    Cache-Oblivious Algorithms: Medians & MatricesNot yet

    Watch on YouTube ↗
  34. Lec 24

    Cache-Oblivious Algorithms: Searching & SortingNot yet

    Watch on YouTube ↗