算法设计与分析基础

Preface1 Introduction　1.1 What is an Algorithm? 　Exercises 1.1　1.2 Fundamentals of Algorithmic Problem Solving　 Understanding the Problem　 Ascertaining the Capabilities of a Computational Device　 Choosing between Exact and Approximate Problem Solving　 Deciding on Appropriate Data Structures　 Algorithm Design Techniques　 Methods of Specifying an Algorithm　 Proving an Algorithm's Correctness　 Analyzing an Algorithm　 Coding an Algorithm　 Exercises 1.2

Preface1 Introduction　1.1 What is an Algorithm? 　Exercises 1.1　1.2 Fundamentals of Algorithmic Problem Solving　 Understanding the Problem　 Ascertaining the Capabilities of a Computational Device　 Choosing between Exact and Approximate Problem Solving　 Deciding on Appropriate Data Structures　 Algorithm Design Techniques　 Methods of Specifying an Algorithm　 Proving an Algorithm's Correctness　 Analyzing an Algorithm　 Coding an Algorithm　 Exercises 1.2　1.3 Important Problem Types　 Sorting　 Searching　 String Processing　 Graph Problems　 Combinatorial Problems　 Geometric Problems　 Numerical Problems　 Exercises 1.3　1.4 Fundamental Data Structures　 Linear Data Structures　 Graphs　 Trees　 Sets and Dictionaries　 Exercises 1.4　 Summary2 Fundamentals of the Analysis of Algorithm Efficiency　2.1 Analysis Framework　 Measuring an Input's Size　 Units for Measuring Running -[]me　 Orders of Growth　 Worst-Case, Best-Case, and Average-Case Efficlencies　 Recapitulation of the Analysis Framework　 Exercises 2.1　2.2 Asymptotic Notations and Basic Efficiency Classes　 Informal Introduction　 O-notation　 9-notation　 Onotation　 Useful Property Involving the Asymptotic Notations　 Using Limits for Comparing Orders of Growth　 Basic Efficiency Classes　 Exercises 2.2　 2.3 Mathematical Analysis of Nonrecursive Algorithms　 Exercises 2.3　 2.4 Mathematical Analysis of Recursive Algorithms　 Exercises 2.4　 2.5 Example: Fibonacci Numbers　 Explicit Formula for the nth Fibonacci Number　 Algorithms for Computing Fibonacci Numbers　 Exercises 2.53 Brute Force4 Divide-and-Conquer5 Decrease-and-Conquer6 Transform-and-Conquer7 Space and lime Tradeoffs8 Dynamic Programming9 Greedy Technique10 Iterative Improvement11 Limitations of Algorithm Power12 Coping with the Limitations of Algorithm PowerEpilogueAPPENDIX AUseful Formulas for the Analysis of AlgorithmsAPPENDIX BShort Tutorial on Recurrence RelationsBibliographyHints to ExercisesIndex

本书采用了一种算法设计技术的新分类方法，不但比传统分类法包容性更强，而且更直观，也更有效，因此广受好评。 这种分类框架条理清晰，契合教育学原理，非常适合算法教学。网上提供了详尽的教学指南供教师和学生下载，书中还为学生安排了习题提示和每章小结。为了提高学习兴趣，书中应用了许多流行的谜题和游戏，需要重点思考的地方则往往会用反问来提醒注意。