跳到主要内容
步芽

【极致中配】密歇根大学 EECS 477 算法导论 Introduction to Algorithms (Winter 2025)

密歇根EECS 477研究生算法课，系统讲授分治、动态规划、最短路、摊还分析、哈希、亚线性与随机化算法、最大流、线性规划、近似与在线算法及乘性权重更新。

难度
难度 5/5 — 研究生级算法课，涵盖亚线性、LP对偶、乘性权重等高级主题，需扎实理论基础
适合人群
有算法基础、想深入高级算法理论的CS本科高年级或研究生
前置要求
数据结构与基础算法（排序、图、堆、递归等）、离散数学与概率（随机化算法与哈希分析必备）、线性代数（理解FFT与线性规划）、渐近分析（大O、摊还分析基础）
课程规模
27 讲 · 1254播放
在 B 站免费观看 →就这门课提问 →排进我的学习路线

主题覆盖

分治与FFT动态规划最短路径摊还分析哈希亚线性算法随机化算法最大流最小割线性规划与对偶近似算法在线算法乘性权重更新

课程大纲（27 讲）

  1. P1 · Lecture 0: Introduction39 分钟
  2. P2 · Lecture 1.1: Divide & Conquer: Polynomial multiplication via FFT41 分钟
  3. P3 · Lecture 1.2: Divide & Conquer: FFT (Continued) Selection, Maximum independent se43 分钟
  4. P4 · Lecture 2.1: Dynamic Programming: Annihilation Method, Task Selection, Edit Dist42 分钟
  5. P5 · Lecture 2.2: Dynamic Programming: Maximum Independent Set on Trees, Traveling Sa41 分钟
  6. P6 · Lecture 3.1: Shortest Paths: Bellman-Ford, Path-doubling, Floyd-Warshall, Intuit44 分钟
  7. P7 · Lecture 3.2: Shortest Paths: Dijkstra, Even-Shiloach Tree for Dynamic Shortest P46 分钟
  8. P8 · Lecture 4.1: Amortized Analysis: Bank account method, Binomial heaps, Hollow hea47 分钟
  9. P9 · Lecture 4.2: Amortized Analysis: Potential function method, Splay trees, Dynamic47 分钟
  10. P10 · Lecture 5.1: Hashing: Probability Primer, Hashing with chaining, Universal hashi43 分钟
  11. P11 · Lecture 5.2: Hashing: Perfect hashing, Cuckoo hashing42 分钟
  12. P12 · Lecture 6.1: Sublinear algorithms: Streaming algorithms for distinct elements43 分钟
  13. P13 · Lecture 6.2: Sublinear algorithms: Sublinear-time Vertex Coloring, Luby's Distri45 分钟
  14. P14 · Lecture 7: Randomization: Median-of-Means trick, Streaming norm estimation (Tug-39 分钟
  15. P15 · Lecture 8.1: Maximum Flows: Ford-Fulkerson and Dinic's algorithm, Maxflow-Mincut46 分钟
  16. P16 · Lecture 8.2: Maximum Flows: Edge/vertex connectivity, Maximum matching, Circulat45 分钟
  17. P17 · Lecture 9.1: Linear Programming: Linear programs and LP duality41 分钟
  18. P18 · Lecture 9.2: Linear Programming: Max-flow Min-cut via LP duality, Intro Approxim43 分钟
  19. P19 · Lecture 10.1: Approximation: Greedy and LP rounding (Set cover, Congestion Minim45 分钟
  20. P20 · Lecture 10.2: Approximation: Primal-Dual Method (f-frequency Set Cover, Feedback43 分钟
  21. P21 · Lecture 11.1: Online Algorithm: Ski rental, Balanced Scheduling, Lower Bound for35 分钟
  22. P22 · Lecture 11.2: Online Algorithms: Online LP Rounding Schemes for Ski Rental and O44 分钟
  23. P23 · Lecture 12.1: Multiplicative Weights Update: Expert Game, No Regret Guarantee43 分钟
  24. P24 · Lecture 12.2: Multiplicative Weights Update: Solving Packing-Covering LP via MWU46 分钟
  25. P25 · Lecture 13.1: Multiplicative Weights Update: Solving Packing-Covering LP via MWU44 分钟
  26. P26 · Lecture 13.2: Multiplicative Weights Update: Width Reduction for the Oracle in M41 分钟
  27. P27 · Lecture 14: Review and Conclusion42 分钟

本课程卡由 AI 生成，可能存在误差，欢迎反馈。