算法设计与分析是计算机专业的核心课程。学习该课程对学习其他专业课奠定了扎实的基础，也对培养计算思维和求解问题的能力起到重要作用。面对各个应用领域的大量实际问题，最重要的是分析问题的性质并选择正确的求解思路，即找到一个好的算法。特别是在当今复杂、海量信息的大数据处理中，一个好的算法往往起到决定性的作用。
    本课程注重针对实际问题需求，进行数学建模并选择高效求解算法的训练，为提高学生的素质和创新能力打下必要的基础。课程主要内容涉及：面对实际问题建立数学模型、设计正确的求解算法、算法的效率估计、改进算法的途径、问题计算复杂度的估计、难解问题的确定和应对策略等等。本课程是算法课程的基础部分，主要涉及算法的设计、分析与改进途径，其他有关计算复杂性的内容将在后续课程"算法设计与分析（高级）"中加以介绍。

    课程的内容分成两大部分：算法的基础知识和通用算法设计技术与分析方法。

    算法基础知识部分主要介绍算法相关的基本概念和数学基础。比如，什么是算法的伪码描述？什么是算法最坏情况下和平均情况下的时间复杂度？算法时间复杂度函数的主要性质，算法复杂度估计中常用的数学方法，如序列求和及递推方程求解。

    通用算法设计技术与分析方法部分主要介绍分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术。重点介绍这些设计技术的使用条件、分析方法、改进途径，并给出一些重要的应用。

线上作业练习考试仅供学习参考，成绩评定根据课程教学计划要求评定。

程序设计基础、数据结构与算法、高等数学、高等代数

第一周 基础知识（1）：算法的基本概念及伪码描述，函数的渐近的界

1.4 货郎问题与计算复杂性

1.1 本周教学内容简介

1.2 算法设计的两个例子

1.6 算法的伪码表示

1.5 算法及其时间复杂度

1.9 几类重要函数

1.7 函数的渐近的界

1.3 问题的计算复杂度：排序问题

1.8 有关函数渐近的界的定理

作业测验

第二周 基础知识（2）：序列求和方法，递推方程求解

2.8 主定理的应用

2.4 迭代法求解递推方程

2.6 递归树

2.7 主定理及其证明

2.2 序列求和的方法

2.1 本周教学内容简介

2.3 递推方程与算法分析

2.5 差消法化简递推方程

作业测验

第三周 分治策略（1）

3.1 本周教学内容简介

3.6 幂乘算法及应用

3.7 改进分治算法的途径1：减少子问题数

3.5 快速排序

3.2 分治策略的设计思想

3.8 改进分治算法的途径2：增加预处理

3.3 分治策略的一般描述和分析方法

3.4 芯片测试

作业测验

第四周 分治策略（2）

4.4 一般选择问题的算法设计

4.7 卷积计算

4.8 快速傅立叶变换FFT算法

4.5.选择问题的算法分析

4.6 卷积及应用

4.1 本周内容简介

4.3 选第二大

4.9 平面点集的凸包

4.2 选最大与最小

作业测验

第五周 动态规划（1）

作业测验

5.1 本周教学内容简介

5.4 动态规划算法的递归实现

5.3 动态规划算法设计

5.7 背包问题

5.2 动态规划算法的例子

5.6 投资问题

5.8 最长公共子序列

5.5 动态规划算法的迭代实现

作业测验

第六周 动态规划（2）

6.3 最大子段和

6.7 序列比对

6.4 最优二叉检索树的概念

6.5 最优二叉检索树的算法

6.2 图像压缩

6.6 RNA二级结构预测

6.1 本周教学内容简介

作业测验

第七周 贪心法（1）

作业测验

7.3 贪心法的正确性证明

7.4 最优装载问题

7.6 得不到最优解的处理方法

7.5 最小延迟调度

7.2 贪心法的例子

7.1 本周教学内容简介

第八周 贪心法（2）

8.5 Prim算法

8.7 单源最短路径问题及算法

单元作业

8.4 最小生成树

8.1 本周教学内容简介

8.6 Kruskal算法

8.2 最优前缀码及哈夫曼算法

8.3 哈夫曼算法的正确性证明

8.8 Dijkstra算法的证明

第九周 回溯与分支限界（1）

9.4 回溯算法实现及实例

作业测试

9.1 本周教学内容简介

9.3 回溯算法的设计思想和适用条件

9.6 搜索树结点数的估计

9.2 几个回溯算法的例子

9.5 图的着色

第十周 回溯与分支限界

10.2 分支限界

10.4 货郎问题

作业测试

10.1 本周教学内容简介

10.7 课程总结

10.6 连续邮资问题

10.5 圆排列问题

10.3 最大团问题

《算法设计与分析（第2版）》  屈婉玲、刘田、张立昂、王捍贫编著 清华大学出版社