Learn · Introduction to Algorithms (SMA 5503)

Lecture 4 of 23Video Lectures1 h 21 min

Lecture 4: Quicksort, Randomized Algorithms

Prof. Charles Leiserson and Prof. Erik Demaine · Massachusetts Institute of Technology

At MIT OpenCourseWare Transcript

Credits and licence

From
Introduction to Algorithms (SMA 5503), 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. Charles Leiserson, Prof. Erik Demaine. Introduction to Algorithms (SMA 5503). Fall 2005. 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: Administrivia; Introduction; Analysis of Algorithms, Insertion Sort, Mergesort 1 h 21 min · Video
  2. Lecture 2: Asymptotic Notation; Recurrences; Substitution, Master Method 1 h 11 min · Video
  3. Lecture 3: Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication 1 h 9 min · Video
  4. Lecture 4: Quicksort, Randomized Algorithms 1 h 21 min · Video
  5. Lecture 5: Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort 1 h 17 min · Video
  6. Lecture 6: Order Statistics, Median 1 h 9 min · Video
  7. Lecture 7: Hashing, Hash Functions 1 h 18 min · Video
  8. Lecture 8: Universal Hashing, Perfect Hashing 1 h 20 min · Video
  9. Lecture 9: Relation of BSTs to Quicksort - Analysis of Random BST 1 h 22 min · Video
  10. Lecture 10: Red-black Trees, Rotations, Insertions, Deletions 1 h 24 min · Video
  11. Lecture 11: Augmenting Data Structures, Dynamic Order Statistics, Interval Trees 1 h 24 min · Video
  12. Lecture 12: Skip Lists 1 h 26 min · Video
  13. Lecture 13: Amortized Algorithms, Table Doubling, Potential Method 1 h 20 min · Video
  14. Lecture 14: Competitive Analysis: Self-organizing Lists 1 h 15 min · Video
  15. Lecture 15: Dynamic Programming, Longest Common Subsequence 1 h 12 min · Video
  16. Lecture 16: Greedy Algorithms, Minimum Spanning Trees 1 h 25 min · Video
  17. Lecture 17: Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search 1 h 25 min · Video
  18. Lecture 18: Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints 1 h 18 min · Video
  19. Lecture 19: Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson 1 h 16 min · Video
  20. Lecture 22: Advanced Topics 1 h 16 min · Video
  21. Lecture 23: Advanced Topics (cont.) 1 h 17 min · Video
  22. Lecture 24: Advanced Topics (cont.) 1 h 25 min · Video
  23. Lecture 25: Advanced Topics (cont.) - Discussion of Follow-on Classes 1 h 26 min · Video