MIT 6.5220 Randomized Algorithms Fall 2025

课程大纲（31 讲）

1. P1 · Lecture 1 Introduction to Randomized Algorithms. Quicksort, BSP96 分钟
2. P2 · Lecture 2 Min-cut, Complexity theory98 分钟
3. P3 · Lecture 3 Adelman's theorem, Game tree evaluation87 分钟
4. P4 · Lecture 4 Game theory, Lower Bounds 1, Coupon Collecting, Stable Matching96 分钟
5. P5 · Lecture 5 Deviations： Markov, Chebyshev. Balls in Bins95 分钟
6. P6 · Lecture 6 Median finding. Pseudorandom numbers78 分钟
7. P7 · Lecture 7： Chernoff Bound. Randomized routing92 分钟
8. P8 · Lecture 8： The power of two choices80 分钟
9. P9 · Lecture 10： 2 Choices (cont). Cuckoo Hashing85 分钟
10. P10 · Lecture 11： Consistent Hashing. Fingerprinting87 分钟
11. P11 · Lecture 12： Text search. Bloom filters84 分钟
12. P12 · Lecture 13： Fingerprinting by polynomials, perfect matching, network coding93 分钟
13. P13 · Lecture 14： Symmetry breaking. Parallel Algorithms. Ethernet. Perfect matching90 分钟
14. P14 · Lecture 16： Parallel Maximal Independent Set. Derandomization92 分钟
15. P15 · Lecture 18 Sampling： transitive closure. DNF counting, rare events92 分钟
16. P16 · Lecture 19 Counting versus generation. Minimum spanning tree92 分钟
17. P17 · Lecture 20 Min-cuts： recursive contraction algorithm85 分钟
18. P18 · Lecture 21 Min-cuts： Sampling Minimum Cuts78 分钟
19. P19 · Lecture 22 Sampling Cuts. Network Reliability92 分钟
20. P20 · Lecture 23 Computational Geometry. Point Location in arrangements of lines92 分钟
21. P21 · Lecture 24 Convex hull via randomized incremental construction. LP87 分钟
22. P22 · Lecture 25： Linear programming by sampling93 分钟
23. P23 · Lecture 26： Linear Programming73 分钟
24. P24 · Lecture 27： LP (Simplex). The Probabilistic Method81 分钟
25. P25 · Lecture 28 Randomized Rounding80 分钟
26. P26 · Lecture 29 Embeddings80 分钟
27. P27 · Lecture 30 Metric Embeddings 292 分钟
28. P28 · Lecture 31 Metric Embeddings; Markov chains 187 分钟
29. P29 · Lecture 32 Markov chains 2： random walks87 分钟
30. P30 · Lecture 33 Markov chains 384 分钟
31. P31 · Lecture 34 Markov chains 479 分钟