Programming Pearls by Bentley, Jon -- Read -- Imperial Library of Trantor

Index

About This E-Book Title Page Copyright Page Preface

About the Book The Code To Readers of the First Edition Acknowledgments for the First Edition Acknowledgments for the Second Edition

Contents Part I: Preliminaries

Column 1: Cracking the Oyster

1.1 A Friendly Conversation 1.2 Precise Problem Statement 1.3 Program Design 1.4 Implementation Sketch 1.5 Principles 1.6 Problems 1.7 Further Reading

Column 2: Aha! Algorithms

2.1 Three Problems 2.2 Ubiquitous Binary Search 2.3 The Power of Primitives 2.4 Getting It Together: Sorting 2.5 Principles 2.6 Problems 2.7 Further Reading 2.8 Implementing an Anagram Program [Sidebar]

Column 3: Data Structures Programs

3.1 A Survey Program 3.2 Form-Letter Programming 3.3 An Array of Examples 3.4 Structuring Data 3.5 Powerful Tools for Specialized Data 3.6 Principles 3.7 Problems 3.8 Further Reading

Column 4: Writing Correct Programs

4.1 The Challenge of Binary Search 4.2 Writing the Program 4.3 Understanding the Program 4.4 Principles 4.5 The Roles of Program Verification 4.6 Problems 4.7 Further Reading

Column 5: A Small Matter of Programming

5.1 From Pseudocode to C 5.2 A Test Harness 5.3 The Art of Assertion 5.4 Automated Testing 5.5 Timing 5.6 The Complete Program 5.7 Principles 5.8 Problems 5.9 Further Reading 5.10 Debugging [Sidebar]

Part II: Performance

Column 6: Perspective on Performance

6.1 A Case Study 6.2 Design Levels 6.3 Principles 6.4 Problems 6.5 Further Reading

Column 7: The Back of the Envelope

7.1 Basic Skills 7.2 Performance Estimates 7.3 Safety Factors 7.4 Little’s Law 7.5 Principles 7.6 Problems 7.7 Further Reading 7.8 Quick Calculations in Everyday Life [Sidebar]

Column 8: Algorithm Design Techniques

8.1 The Problem and a Simple Algorithm 8.2 Two Quadratic Algorithms 8.3 A Divide-and-Conquer Algorithm 8.4 A Scanning Algorithm 8.5 What Does It Matter? 8.6 Principles 8.7 Problems 8.8 Further Reading

Column 9: Code Tuning

9.1 A Typical Story 9.2 A First Aid Sampler 9.3 Major Surgery — Binary Search 9.4 Principles 9.5 Problems 9.6 Further Reading

Column 10: Squeezing Space

10.1 The Key — Simplicity 10.2 An Illustrative Problem 10.3 Techniques for Data Space 10.4 Techniques for Code Space 10.5 Principles 10.6 Problems 10.7 Further Reading 10.8 A Big Squeeze [Sidebar]

Part III: The Product

Column 11: Sorting

11.1 Insertion Sort 11.2 A Simple Quicksort 11.3 Better Quicksorts 11.4 Principles 11.5 Problems 11.6 Further Reading

Column 12: A Sample Problem

12.1 The Problem 12.2 One Solution 12.3 The Design Space 12.4 Principles 12.5 Problems 12.6 Further Reading

Column 13: Searching

13.1 The Interface 13.2 Linear Structures 13.3 Binary Search Trees 13.4 Structures for Integers 13.5 Principles 13.6 Problems 13.7 Further Reading 13.8 A Real Searching Problem [Sidebar]

Column 14: Heaps

14.1 The Data Structure 14.2 Two Critical Functions 14.3 Priority Queues 14.4 A Sorting Algorithm 14.5 Principles 14.6 Problems 14.7 Further Reading

Column 15: Strings of Pearls

15.1 Words 15.2 Phrases 15.3 Generating Text 15.4 Principles 15.5 Problems 15.6 Further Reading

Epilog to the First Edition Epilog to The Second Edition Appendix 1: A Catalog of Algorithms

Sorting Searching Other Set Algorithms Algorithms on Strings Vector and Matrix Algorithms Random Objects Numerical Algorithms

Appendix 2: An Estimation Quiz Appendix 3: Cost Models for Time and Space Appendix 4: Rules for Code Tuning

Space-For-Time Rules Time-For-Space Rules Loop Rules Logic Rules Procedure Rules Expression Rules

Appendix 5: C++ Classes for Searching Hints for Selected Problems

Column 1 Column 2 Column 3 Column 4 Column 5 Column 6 Column 7 Column 8 Column 9 Column 10 Column 11 Column 12 Column 13 Column 14 Column 15

Solutions to Selected Problems

Solutions for Column 1 Solutions for Column 2 Solutions for Column 3 Solutions for Column 4 Solutions for Column 5 Solutions for Column 6 Solutions for Column 7 Solutions for Column 8 Solutions for Column 9 Solutions for Column 10 Solutions for Column 11 Solutions for Column 12 Solutions for Column 13 Solutions for Column 14 Solutions for Column 15

Index Code Snippets