CONTENTS Part I: PRELIMINARIES 1 Column 1: Cracking the Oyster 3 A Friendly Conversation ~ Precise Problem Statement ~ Program Design ~ Implementation Sketch. Principles ~ Problems. Further Reading Column 2: Aha! Algorithms 11 Three Problems ~ Ubiquitous Binary Search ~ The Power of Primitives ~ Getting It Together: Sorting. Principles. Problems. Further Reading. Implementing an Anagram Program Column 3: Data Structures Programs 21 A Survey Program ~ Form-Letter Programming ~ An Array of Examples ~ Structuring Data. Powerful Tools for Specialized Data ~ Principles ~ Prob- lems ~ Further Reading Column 4: Writing Correct Programs 33 The Challenge of Binary Search ~ Writing the Program ~ Understanding the Program. Principles ~ The Roles of Program Verification ~ Problems. Further Reading Column 5: A Small Matter of Programming 45 From Pseudocode to C ~ A Test Harness ~ The Art of Assertion ~ Auto- mated Testing ~ Timing ~ The Complete Program. Principles ~ Problems ~ Further Reading ~ Debugging Part II: PERFORMANCE 59 Column 6: Perspective on Performance 61 A Case Study. Design Levels. Principles. Problems ~ Further Reading Column 7: The Back of the Envelope 67 Basic Skills ~ Performance Estimates ~ Safety Factors ~ Little's Law ~ Principles ~ Problems ~ Further Reading ~ Quick Calculations in Everyday Life Column 8: Algorithm Design Techniques 77 The Problem and a Simple Algorithm ~ Two Quadratic Algorithms ~ A Divide-and-Conquer Algorithm ~ A Scanning Algorithm ~ What Does It Matter? ~ Principles. Problems. Further Reading Column 9: Code Tuning 87 A Typical Story ~ A First Aid Sampler ~ Major Surgery Binary Search ~ Principles. Problems. Further Reading Column 10: Squeezing Space 99 The Key Simplicity ~ An Illustrative Problem. Techniques for Data Space. Techniques for Code Space ~ Principles ~ Problems ~ Further Reading ~ A Big Squeeze Part III: THE PRODUCT 113 Column 11: Sorting 115 Insertion Sort ~ A Simple Quicksort ~ Better Quicksorts ~ Principles ~ Problems ~ Further Reading Column 12: A Sample Problem 125 The Problem ~ One Solution. The Design Space. Principles ~ Problems ~ Further Reading Column 13: Searching 133 The Interface ~ Linear Structures ~ Binary Search Trees ~ Structures for Integers. Principles. Problems. Further Reading. A Real Searching Problem Column 14: Heaps 147 The Data Structure ~ Two Critical Functions ~ Priority Queues ~ A Sorting Algorithm. Principles. Problems. Further Reading Column 15: Strings of Pearls 161 Words ~ Phrases ~ Generating Text ~ Principles ~ Problems ~ Further Reading Epilog to the First Edition 175 Epilog to the Second Edition 177 Appendix 1: A Catalog of Algorithms 179 Appendix 2: An Estimation Quiz 183 Appendix 3: Cost Models for Time and Space 185 Appendix 4: Rules for Code Tuning 191 Appendix 5: C++ Classes for Searching 197 Hints for Selected Problems 201 Solutions to Selected Problems 205 Index 233