课程号：00110060
课程名称：算法设计与分析
开课学期：秋
学分： 3
先修课程：，高等数学，数据结构，离散数学，概率论
基本目的：本课程通过系列典型问题阐释计算机算法的重要设计策略：贪心法，分治法，动态规划法，图检索和周游方法，回溯法等，同时概述分析算法时间复杂度和效率的方法，并简要介绍NP难度问题及相应的近似算法和随机算法。期望学生掌握算法评估的基本原理与方法；提高设计新算法的能力。
内容提要：
第一章：引言（约2学时）
1)计算机算法的概念，算法评判的准则，时间复杂度与空间复杂度的计算，复杂度的渐近分析，多项式复杂度算法和指数复杂度算法，可行算法；2)算法语言：SPARKS
第二章：分治法 （约10学时）
1)分治法的原理，整数位乘，Strassen 矩阵乘法，快速Fourier变换；2)时间复杂度的递归表达式，Master 定理；3)二分检索算法；4)选择问题：找最大和最小元素；找最大和次大元素，对手策略；5)排序问题：插入排序；堆排序，归并排序；快速排序，排序算法时间复杂度的下界估计，排序算法的优劣性比较；6）计算几何问题：最近点对问题和凸包问题
第三章：贪心法（约6学时）
1)最优化问题的框架，贪心法的思路，最小生成树的Kruskal算法；2)磁带上的最优存储，最小延迟；3)背包问题；4)带有限期的作业调度；5)拟阵与贪心算法；6）最优根树
第四章：动态规划法（约8学时）
1)多阶段问题与最优性原理，矩阵连乘问题；2）最优二分检索树；3)最长递增子序列；4）0/1背包问题；5）流水线调度问题；6）最长非递减子序列
第五章：基本周游与检索方法（约8学时）
1)宽度优先检索与最少操作问题；2）深度优先检索，有向图的拓扑序，关键路径；3）有向图的强连通分图与无向图的双连通分图
第六章：回溯法（约4时）
1) 回溯法原理，骑士巡游问题；2)稳定婚姻问题
专题选讲（约6学时）
1）平摊分析；2）NP-难度和NP-完全问题简介；3）近似算法和随机算法简介
教学方式：每周授课3学时
教材与参考书：
1. 余祥宣，崔国华，邹海明，“计算机算法基础”，华中科技大学出版社，1998。
2. E. Horowitz, S. Sahni, “Fundamentals of Computer Algorithms”, New York: Computer Science Press, Pitman, Inc., 1978.
3. Sara Baase, Allen Van Gelder, “Computer Algorithms: Introduction to Design and Analysis (Third Edition)”, Higher Education Press & Pearson Education Asia Limited., 2001.
4. Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, “Introduction to Algorithms (Second Edition)”, Higher Education Press & The MIT Press, 2002. （有中译本）
5. D. E. Knuth, “The Art of Computer Programming (Third Edition): Fundamental Algorithms (Vol. 1)”, Addison-Wesley, 1998; 清华大学出版社（影印），2002.
6. D. E. Knuth, “The Art of Computer Programming (Third Edition): Sorting and Searching (Vol. 3)”, Addison-Wesley, 1998; 清华大学出版社（影印），2002.
7. Jon Kleinberg and Eva Tardos, “Algorithm Design”, Pearson Education Asia Limited and Tsinghua Unversity Press, 2006.（有中译本）
8. M H Alsuwaiyel, Algorithms: Design Techniques and Analysis (Revised Edition), World Scientific Publishing Co. Pte. Ltd., 2016.
学生成绩评定方法：作业20％，期末考试80％.
课程修订负责人：杨建生
