算法导论

南京大学,继续教育学院,计算机科学与技术系2013级

上课时间:2014年9月1日 至 2015年1月4日 (共18周) 考试时间:2015年1月5日 至 2015年1月18日 (共2周)

第1章 算法引论 [pdf版本讲义]

第2章 递归与分治策略 [pdf版本讲义]

注:在这一讲中介绍递归的实现机制时,我们使用了算法对应的程序执行时的现场这一术语,而在计算机界,现场这一术语往往指通用寄存器中的值。由于在进行算法描述时,我们基于抽象的计算机模型,不涉及具体的计算机体系结构和机器级指令的执行,因此我们在本课程借用了现场这一概念。在这一讲中我们所指的现场,是指函数的所有局部变量的值。

第3讲 选择问题(第一章习题讲解与编程示例)[pdf版本讲义][选择最大值的C代码][选择最大值的Java代码]

勘误:在本讲最后的作业中,2.4小题隐含要求同学们在2.3小题决策树的结果上,圈出第3小的值的范围。事实上,无法保证第3小的值进入选择第2小的值的决策树,因此此题假设有误。举例来说,若输入的数组为[5, 6, 17, 63, 52, 47, 3, 7, 79, 86],则原本第3小的值6会在第一轮就被第2小的值5比下去,从而无法进入选择第2小的值的决策过程。我在出题时出现了疏漏,在此表示歉意。非常感谢吴同学给我指出问题!

第4讲 基本数据结构[pdf版本讲义]

第5讲 动态规划入门[pdf版本讲义]

第6讲 动态规划第二讲[pdf版本讲义]

第7讲 动态规划和贪心法[pdf版本讲义][0-1背包问题算法C代码]

第8讲 贪心法[pdf版本讲义]

第9讲 图论算法[pdf版本讲义]

第10讲 图论算法第二讲[pdf版本讲义]

第11讲 旅行商问题与NP完全性理论[pdf版本讲义]

第12讲 回溯法[pdf版本讲义]

第13讲 习题课1[pdf版本讲义]

第14讲 习题课2[pdf版本讲义]

第15讲 习题课3[pdf版本讲义]

第16讲 习题课4[pdf版本讲义]