| 1 |
课程介绍
斐波那契堆 |
|
| 2 |
最小生成树
持久数据结构 |
|
| 3 |
伸展树 |
|
| 4 |
伸展树(续)
后缀树
Tries树 |
习题集 1 |
| 5 |
后缀树(续)
Tries树 (续)
Dial 算法 |
|
| 6 |
Dijkstra算法
Van Emde Boas队列 |
习题集 2 |
| 7 |
Van Emde Boas 队列(续)
哈希表 |
|
| 8 |
2-级哈希
网络流 |
|
| 9 |
网络流：增广路径，最大增广路径，缩放法 |
习题集 3 |
| 10 |
流问题的化简
双向匹配
最短增广路径
阻塞流 |
|
| 11 |
阻塞流(续) |
|
|
回顾主题：动态树、压入-重标记最大流算法 |
|
| 12 |
最小代价流 |
习题集 4 |
| 13 |
最小代价流(续)
线性规划 |
习题集 5 |
| 14 |
线性规划(续)
优化结构
弱对偶性 |
|
| 15 |
线性规划(续)
强对偶性 |
|
|
回顾主题: 简单化 |
习题集 6 |
| 16 |
线性规划(续)
互补松弛性
算法：简单性， Ellipsoid |
|
| 17 |
线性规划(续)
算法：内部点
NP-难问题 |
习题集7 在讲座17后两天内交 |
| 18 |
近似算法 |
|
| 19 |
旅行商问题的4/3-近似 |
|
| 20 |
松弛法
有向旅行商问题 |
习题集 8 |
| 21 |
随机舍入算法
切尔诺夫上界问题
固定参数Tractability算法
核化算法 |
|
| 22 |
在线算法(雪撬租约, 负载平衡, 分页) |
习题集 9 |
| 23 |
随机在线算法(Adversaries, Fiat氏标记算法,势能函数,姚氏最小最大化原则) |
|
| 24 |
K-服务器问题
双-覆盖算法
计算几何介绍(垂直范围搜索) |
习题集 10 |
| 25 |
扫描线算法(凸包,线段交集 , 维氏图) |
|
| 26 |
扫描线算法(维氏图)
随机增量构建
后向分析
固定维的线性规划算法 |
习题集11 在讲座26后两天交 |
| 27 |
(可选材料)外部存储器算法 |
习题集12 ,习题1 |
| 28 |
(可选材料) 缓存忽略算法: 矩阵相乘,链接表,平均值 |
|
| 29 |
(可选材料) 缓存忽略算法: 查找
流模式 |
习题集12的剩余部分在讲座29后上交 |