1 Introduction 1.1 What Is an Algorithm? Exercises 1.1 1.2 Fundamentals o Aorithmic Problem Solving Understanding the Problem Ascertaining the Capabilities of the Computational Device Choosing between Exact and Approximate Problem Solving Algorithm Design Techniques Designing an Algorithm and Data Structures 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 Exerises 1.4 Summary
2 Fundamentals of the Analysis o Aorithm Efficiency 3 Brute Force and Exhaustive Search 4 Decrease-and-Conquer 5 Divide-and-Conquer 6 Transform-and-Conquer 7 Space and Time Trade-Offs 8 Dynamic Programming 9 Greedy Technique 10 Iterative Improvement 11 Limitations o Aorithm Power 12 Coping with the Limitations o Aorithm Power
Epilogue APPENDIX A Useful Formulas for the Analysis o Aorithms Properties of Logarithms Combinatorics Important Summation Formulas Sum Manipulation Rules Approximation of a Sum by a Definite Integral Floor and Ceiling Formulas Miscellaneous APPENDIX B Short Tutorial on Recurrence Relations Sequences and Recurrence Relations Methods for Solving Recurrence Relations Common Recurrence Types in Algorithm Analysis References Hints to Exercises Index