时间：1-16周，每周周五5-6节
地点：地学楼 102
助教：岳镝（邮箱：di_yue@stu.pku.edu.cn，手机号/微信：18380578521）
参考资料： 北大网盘
| 周 | 大班 | 小班 | |
|---|---|---|---|
| 周一 | 周三 | ||
| 1 | 引言：介绍课程的教学目标、主要内容、教学安排等 | 数学基础：函数及其阶的估计、求和 | |
| 2 | 递推方程的求解方法：迭代、递归树、主定理 | 分治策略1 |
贾润东：分治策略1 |
| 3 | 分治策略2 | 动态规划1 |
李嘉鹤：分治策略2 梅志垒：动态规划1 |
| 4 | 动态规划2 | 贪心算法1 |
陈莹蔚：动态规划2 徐来：贪心算法1 |
| 5 | 贪心算法2 | 回溯算法设计步骤（皇后问题、装载问题）、效率估计 |
陈建豪：贪心算法2 |
| 6 | 分支限界及应用 | 线性规划，单纯型法 |
梁可欣：分支限界及应用 姬忠杭：线性规划，单纯型法 |
| 7 | 对偶性，整数规划的分支限界（简要介绍） | 平摊分析 | 清明节放假 |
| 8 | 期中复习 | 期中考试 |
石中玉：平摊分析 |
| 9 | 最大流问题Ford-Fulkson算法 | Dinic算法，最小费用流 | |
| 10 | 最大流的应用 | 问题的复杂度分析：分析方法、决策树、检索问题算法复杂度下界 |
阿玛歌兰：最大流的应用 |
| 11 | 排序问题算法复杂度下界 | 选择问题算法复杂度下界，归约 | 五一放假 |
| 12 | 五一放假 | 五一放假 |
康俊杰：排序问题算法复杂度下界 李宸玥：选择问题算法复杂度下界，归约 |
| 13 | NP完全性理论简介 | 几个基本的NP完全问题及应用：多机调度的子问题分析、优化问题难度界定 |
王子睿：NP 完全性理论简介 |
| 14 | 近似算法：装箱问题、多机调度、货郎问题 | 近似算法：背包问题及多项式时间近似方案 | |
| 15 | 随机快速排序算法、随机选择随机算法 | 随机算法：串匹配、RSA公钥密码的素数测试 | |
| 16 | 端午节放假 | 期末复习 |
陈文浩：期末复习 |
作业在（大班）教学网布置，并在下表同步。每次作业请在对应的 deadline 之前发送到邮箱 diyue2003@gmail.com（注意不是助教的 pku 邮箱，也请不要通过微信发送，以免遗漏）。作业的参考答案将在下表公布。
| Deadline | 作业 | 参考答案 |
|---|---|---|
| 2/28, 13:00 | 教材习题：1.2、1.3、1.6、1.7、1.8、1.12、1.15(2)(4)、1.18、1.19(2)(4)(6)、1.21 | 作业 1 评分标准 |
| 3/7, 13:00 | 教材习题：2.7，2.9，2.12，2.15，2.16, 2.18，2.23，2.27 | 作业 2 评分标准 |
| 3/14, 13:00 | 教材习题：3.3，3.5， 3.8， 3.10， 3.15， 3.17 | 作业 3 评分标准，大家的其他解法 |
| 3/21, 13:00 | 教材习题：4.1，4.3，4.6，4.13，4.18，4.20 | 作业 4 评分标准 |
| 3/28, 13:00 | 教材习题：5.2，5.5，5.6，5.7 | 作业 5 评分标准 |
| 4/11, 13:00 | 教材习题: 6.2, 6.4 (1) (3), 6.6, 6.13, 6.14 | 作业 6 评分标准 |
| 4/25, 13:00 | 教材习题：7.4，7.7，7.17，7.21(1)，7.22 | 作业 7 评分标准 |
| 5/9, 13:00 | 教材习题：8.2，8.4，8.8，8.9，8.10 | 作业 8 评分标准，8.8 正确做法 |
| 5/23, 13:00 | 教材习题：9.5，9.10，9.14，9.15 | 作业 9 评分标准 |
| 5/30, 13:00 | 作业 10 | 作业 10 评分标准 |