作为问题求解和程序设计的重要基础，算法设计与分析在计算机科学与技术专业的课程体系中是一门重要的必修课. 通过该课程的学习，不但为学习其他专业课程奠定了扎实的基础，而且对培养学生分析与解决问题的能力及计算思维有着不可替代的作用. ACM IEEE Computing Curricula 2004与我国教育部计算机科学与技术专业教学指导委员会提出的《计算机科学与技术专业规范2005》都把该课程列入本专业的核心课程之一.

本书是国家高等教育“十一五”规划教材《算法设计与分析》(清华大学出版社，屈婉玲等)的辅助教材. 主教材包括算法设计、算法分析、计算复杂性理论等重要内容. 结合各种典型应用，主教材首先深入分析了各种算法设计技术的适用范围、设计步骤、正确性证明与复杂度的分析方法、改进算法的途径、局限性等，为从事实际问题求解的算法设计与分析工作在理论上提供清晰的、整体的思路和方法，并在此基础上介绍了问题难度的分析方法和计算复杂性理论的基本框架和一些重要的结果. 

算法具有广泛的应用背景，习题量大，方法灵活. 针对给定算法问题，在建模、设计技术选择、效率分析、改进途径等方面，初学者往往不知道如何着手. 本书在多年算法教学的基础上精选了100多道典型的习题，给出了详尽的解答和分析，以期对初学者有所帮助. 

与主教材配套，本书也分为10章. 第1章是基础知识；第2～5章分别阐述分治策略、动态规划、贪心法、回溯与分支限界等算法设计技术；第6章介绍算法分析和问题的计算复杂度；第7章是NP完全性理论；第8章是近似算法；第9章是随机算法；第10章介绍处理难解问题的策略. 每章首先对所涉及的重要知识点和方法进行总结，然后给出习题和解答.

本书前4章由屈婉玲编写，第5～6章由王捍贫编写，第7～8章由张立昂编写，第9～10章由刘田编写. 

为了提高本书的质量，欢迎广大读者的批评和指正！

作者

2014年3月于北京大学