Part Ⅰ：PRELIMINARIES 1
Column 1:Cracking the Oyster 3
A Friendly ConversationPrecise Problem StatementProgram DesignImplementation SketchPrinciplesProblemsFurther ReadingColumn 2:Aha!Algorithms 11
Three ProblemsUbiquitous Binary SearchThe Power of PrimitivesGetting It Together:SortingPrinciplesProblemsFurther ReadingImplementing an Anagram ProgramColumn 3:Data Structures Programs 21
A Survey ProgramForm-Letter ProgrammingAn Array of ExamplesStructuring DataPowerful Tools for Specialized DataPrinciplesProb-lemsFurther ReadingColumn 4:Writing Correct Programs 33
The Challenge of Binary SearchWriting the ProgramUnderstanding the ProgramPrinciplesThe Roles of Program VerificationProblemsFurther ReadingColumn 5:A Small Matter of Programming 45
From Pseudocode to CA Test Harness·he Art of AssertionAuto-mated TestingTimingThe CompleteProgramPrinciplesProblemsFurther ReadingDebuggingPart Ⅱ：PERFORMANCE 59
Column 6:Perspective on Performance 61
A Case StudyDesign LevelsPrinciplesProblemsFurther ReadingColumn 7:The Back of the Envelope 67
Basic SkillsPerformance EstimatesSafety FactorsLittle's LawPrinciplesProblemsFurther ReadingQuick Calculations in EverydayColumn 8:Algorithm Design Techniques 77
The Problem and a Simple AlgorithmTwo Quadratic AlgorithmsA Divide-and-Conquer AlgorithmA Scanning AlgorithmWhat Does It Matter?PrinciplesProblemsFurther ReadingColumn 9:Code Tuning 87
A Typical StoryA First Aid SamplerMajor Surgery—Binary SearchPrinciplesProblemsFurther ReadingColumn 10:Squeezing Space 99
The Key—SimplicityAn Illustrative ProblemTechniques for Data SpaceTechniques for Code SpacePrinciplesProblemsFurther ReadingA Big SqueezePart Ⅲ：THE PRODUCT 113
Column 11:Sorting 115
Insertion SortA Simple QuicksortBetter QuicksortsPrinciplesProblemsFurther ReadingColumn 12:A Sample Problem 125
The ProblemOne SolutionThe Design SpacePrinciplesProblemsFurther ReadingColumn 13:Searching 133
The InterfaceLinear StructuresBinary Search TreesStructures for IntegersPrinciplesProblemsFurther ReadingA Real Searching ProblemColumn 14:Heaps 147
The Data StructureTwo Critical FunctionsPriority QueuesA Sorting AlgorithmPrinciplesProblemsFurther ReadingColumn 15:Strings of Pearls 161
WordsPhrasesGenerating TextPrinciplesProblemsFurther ReadingEpilog 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