这一部分包含一些不能被屏幕阅读软件所访问的文档。用"#"标识出。
尽管下面的讲稿的一部分是记录的这门课程的2005年版本，但是许多记录笔记是由该门课的 以前的版本
摘过来的。这些老的版本可以被学生访问到。
这些记录都是由学生记录的，使用时必须经过许可。
这些引导笔记通常跨度许多讲座。
讲义文件
| 讲座 # |
主题 |
记录笔记 |
授课教师讲义 |
| 1 |
课程介绍
斐波那契堆 |
斐波那契堆 (PDF)
(Courtesy of David Andersen, Ioana Dumitriu, John Dunagan, and Akshay
Patil.) |
(PDF
1)
(PDF
2) |
| 2 |
最小生成树
持久数据结构 |
持久数据结构(PDF)
(Courtesy of Sommer Gentry and Eddie Kohler.) |
(PDF) |
| 3 |
伸展树 |
伸展树(PDF)(Courtesy
of Xin Zhang.) |
(PDF) |
| 4 |
伸展树 (续)
后缀树
Tries树 | (PDF)
后缀树与斐波那契堆(PDF) |
(PDF) |
| 5 |
后缀树 (续)
Tries树 (续)
Dial算法 |
|
|
| 6 |
Dijkstra算法
Van Emde Boas 队列 |
Van Emde Boas 队列 (PDF)#
(Courtesy of Abhi Shelat, Andrew Menard, and Akshay Patil.) |
(PDF) |
| 7 |
Van Emde Boas 队列 (续)
哈希表 |
|
(PDF) |
| 8 |
2-级哈希
网络流 |
最大流 (PDF)
(Courtesy of Alexandr Andoni.) |
(PDF) |
| 9 |
网络流：增广路径，最大增广路径，缩放法 |
|
|
| 10 |
流问题的化简
双向匹配
最短增广路径
阻塞流 |
|
|
| 11 |
阻塞流 (续) |
|
|
| 12 |
最小代价流 |
最小代价流算法(PDF)
(Courtesy of Wendy Chang.) |
(PDF) |
| 13 |
最小代价流 (续)
线性规划 |
|
(PDF) |
| 14 |
线性规划(续)
最优化结构
弱对偶性 |
对偶性 (PDF)
(Courtesy of Jay-Kumar Sundararajan.) |
|
| 15 |
线性规划 (续)
强对偶性 |
对偶性(PDF)
(Courtesy of Jay-Kumar Sundararajan.) |
|
| 16 |
线性规划 (续)
互补松弛性
算法: 简单性, Ellipsoid |
对偶性 (PDF)
(Courtesy of Jay-Kumar Sundararajan.) |
|
| 17 |
线性规划(续)
算法：内部点 |
|
|
| 18 |
近似算法
NP-难问题 |
|
(PDF) |
| 19 |
旅行商问题的4/3-近似 |
|
|
| 20 |
松弛法
有向旅行商问题 |
|
|
| 21 |
随机舍入法
切尔诺夫边界
固定参数Tractability
核化算法 |
|
(PDF) |
| 22 |
在线算法 (雪撬租约,负载平衡, 分页) |
随机问题的竞争比的下限
在线算法 (PDF)
(Courtesy of Chun-Chieh Lin.) |
(PDF) |
| 23 |
随机在线算法 (对手问题, Fiat标记算法，势能函数，姚氏最小最大化原则 ) |
随机问题的竞争比的下限
在线算法 (PDF)
(Courtesy of Chun-Chieh Lin.) |
|
| 24 |
K-服务器问题
双覆盖面算法
计算几何导论(正交范围查找) |
|
|
| 25 |
扫描线算法(凸包, 线段求交 , Voronoi 图) |
扫描线 (PDF)
(Courtesy of Matt Rasmussen.) |
(PDF) |
| 26 |
扫描线 算法 (Voronoi
图)
随机增长构造
后向分析
在固定维的线性规划 |
|
|
| 27 |
(可选材料) 外存算法 |
|
(PDF) |
| 28 |
(可选材料) 缓存忽略算法: 矩阵相乘, 链接表, 平均值 |
|
|
| 29 |
(可选的材料) 缓存忽略算法: 查找
流模式 |
|
|
| 29 |
(可选材料) 并行算法
|
|
(PDF) |
该课2004年的讲义
课堂讲座
| 讲座 # |
主题 |
记录笔记 |
| 1 |
课程介绍
斐波那契堆 |
(PDF)#
Courtesy of David Andersen,
Ioana Dumitriu, John Dunagan, and Akshay Patil.) |
| 2 |
持久数据结构
后缀树 |
(PDF
1) (Courtesy of Sommer Gentry and Eddie Kohler.)
(PDF
2) (Courtesy of Jiawen Chen.) |
| 3 |
后缀树(续) |
(PDF)# |
| 4 |
Treaps |
|
|
伸展树 |
(PDF)
(Courtesy of Naveen Sunkavally.) |
| 5 |
哈希: 2-统一的, 完美哈希
指印理论 |
|
| 6 |
指印理论 (续)
最大流 |
(PDF
1) (Courtesy of Jiawen Chen.)
(PDF
2) (Courtesy of Alexandr Andoni.) |
| 7 |
最大流 (续) |
|
| 8 |
最大流 (续) |
|
| 9 |
最大流 (最小代价的最大流) |
|
|
动态树
预流-压入 算法 |
|
| 10 |
最小代价流算法
线性规划算法 |
(PDF
1)# (Courtesy of Brian Dean and John Jannotti.)
|
| 11 |
线性规划算法 (续)
Farkas引理
对偶性 |
(PDF)#
(Courtesy of Vinod Vaikuntanathan.) |
|
Goldberg-Tarjan 最小代价流 |
(PDF)#
(Courtesy of Mohammad Hajiaghayi and Vahab Mirrokni.) |
| 12 |
线性规划算法: 更多的对偶性 (弱对偶和强对偶性)
互补松弛条件 |
|
| 13 |
线性规划算法: 互补松弛条件 (与上同) |
|
| 14 |
线性规划算法: 内部点算法
近似算法: 单一近似, 相对近似 |
(PDF)
(Courtesy of Jason Eisenberg.) |
| 15 |
近似算法: PAS, FPAS, 舍入法, 枚举法 |
|
| 16 |
近似算法: 舍入法, 枚举法 |
(PDF)#
(Courtesy of Sachin Katti.) |
| 17 |
近似算法: 线性规划松弛近似,随机舍入 |
(PDF)(Courtesy
of Shannon McDonald.) |
| 18 |
固定参数Tractability |
(PDF)#
(Courtesy of Shannon McDonald.) |
| 19 |
固定参数Tractability - 树宽
在线算法 |
|
| 20 |
在线算法 (续): 分页, 随机化, 势能函数 |
|
| 21 |
随机在线算法 (逆向模型, 标记算法) |
|
| 22 |
随机在线算法的下界
几何学: 范围查找 |
(PDF)#
(Courtesy of Nick Harvey.) |
| 23 |
凸包
Voronoi 图 |
|
| 24 |
Voronoi 图 (续)
随机增长构建法: 二分空间划分 |
|
| 25 |
随机增长构建法的后向分析: 凸包,线性规划 |
|
| 26 |
外存算法 |
|
| 27 |
缓存忽略算法 |
|