Learn · Design and Analysis of Algorithms

Lecture 18 of 34Lecture Videos1 h 18 min

Lecture 18: Complexity: Fixed-Parameter Algorithms

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

At MIT OpenCourseWare Transcript

Credits and licence

From
Design and Analysis of Algorithms, Massachusetts Institute of Technology (at MIT OpenCourseWare)
Licence
CC BY-NC-SA 4.0, as MIT OpenCourseWare states it. Non-commercial use only.
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
Tweens profiles and older. How courses are placed

All the lectures

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