Programming Pearls, 2nd Edition

About

Features

• NEW - .

• .

Description

When programmers list their favourite books, Jon Bentley’s collection of programming pearls is commonly included among the classics. Just as natural pearls grow from grains of sand that irritate oysters, programming pearls have grown from real problems that have irritated real programmers. With origins beyond solid engineering, in the realm of insight and creativity, Bentley’s pearls offer unique and clever solutions to those nagging problems. Illustrated by programs designed as much for fun as for instruction, the book is filled with lucid and witty descriptions of practical programming techniques and fundamental design principles. It is not at all surprising that Programming Pearls has been so highly valued by programmers at every level of experience.

What remains the same in this edition is Bentley’s focus on the hard core of programming problems and his delivery of workable solutions to those problems. Whether you are new to Bentley’s classic or are revisiting his work for some fresh insight, the book is sure to make your own list of favourites.

Downloads

Downloads

Here you can download a .zip which contains source code, teaching material, and samples of the case studies and examples from the book. Instructions: Extract this .zip file locally, then open the index.html file to navigate through the content.

Download the files (797 KB .zip)

Sample Content

Table of Contents

I. PRELIMINARIES.

Column 1. Cracking the Oyster.

A Friendly Conversation.

Precise Problem Statement.

Program Design.

Implementation Sketch.

Principles.

Problems.

Further Reading.

Column 2. Aha! Algorithms.

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.

A Survey Program.

Form-Letter Programming.

An Array of Examples.

Structuring Data.

Powerful Tools for Specialized Data.

Principles.

Problems.

Further Reading.

Column 4. Writing Correct Programs.

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.

From Pseudocode to C.

A Test Harness.

The Art of Assertion.

Automated Testing.

Timing.

The Complete Program.

Principles.

Problems.

Further Reading.

Debugging.

II. PERFORMANCE.

Column 6. Perspective on Performance.

A Case Study.

Design Levels.

Principles.

Problems.

Further Reading.

Column 7. The Back of the Envelope.

Basic Skills.

Performance Estimates.

Safety Factors.

Little's Law.

Principles.

Problems.

Further Reading.

Quick Calculations in Everyday Life.

Column 8. Algorithm Design Techniques.

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.

A Typical Story.

A First Aid Sampler.

Major Surgery—Binary Search.

Principles.

Problems.

Further Reading.

Column 10. Squeezing Space.

The Key—Simplicity.

An Illustrative Problem.

Techniques for Data Space.

Techniques for Code Space.

Principles.

Problems.

Further Reading.

A Big Squeeze.

III. THE PRODUCT.

Column 11. Sorting.

Insertion Sort.

A Simple Quicksort.

Better Quicksorts.

Principles.

Problems.

Further Reading.

Column 12. A Sample Problem.

The Problem.

One Solution.

The Design Space.

Principles.

Problems.

Further Reading.

Column 13. Searching.

The Interface.

Linear Structures.

Binary Search Trees.

Structures for Integers.

Principles.

Problems.

Further Reading.

A Real Searching Problem.

Column 14. Heaps.

The Data Structure.

Two Critical Functions.

Priority Queues.

A Sorting Algorithm.

Principles.

Problems.

Further Reading.

Column 15. Strings of Pearls.

Words.

Phrases.

Generating Text.

Principles.

Problems.

Further Reading.

Epilog to the First Edition.

Epilog to the Second Edition.

Appendix 1. A Catalog of Algorithms.

Appendix 2. An Estimation Quiz.

Appendix 3. Cost Models for Time and Space.

Appendix 4. Rules for Code Tuning.

Appendix 5. C++ Classes for Searching.

Hints for Selected Problems.

Solutions to Selected Problems.

Index. 0201657880T04062001

Preface

Computer programming has many faces. Fred Brooks paints the big picture in The Mythical Man Month; his essays underscore the crucial role of management in large software projects. At a finer grain, Steve McConnell teaches good programming style in Code Complete. The topics in those books are the key to good software and the hallmark of the professional programmer. Unfortunately, though, the workmanlike application of those sound engineering principles isn't always thrilling -- until the software is completed on time and works without surprise.

About the Book
The columns in this book are about a more glamorous aspect of the profession: programming pearls whose origins lie beyond solid engineering, in the realm of insight and creativity. Just as natural pearls grow from grains of sand that have irritated oysters, these programming pearls have grown from real problems that have irritated real programmers. The programs are fun, and they teach important programming techniques and fundamental design principles.

Most of these essays originally appeared in my ''Programming Pearls'' column in Communications of the Association for Computing Machinery. They were collected, revised and published as the first edition of this book in 1986. Twelve of the thirteen pieces in the first edition have been edited substantially for this edition, and three new columns have been added.

The only background the book assumes is programming experience in a high-level language. Advanced techniques (such as templates in C++) show up now and then, but the reader unfamiliar with such topics will be able to skip to the next section with impunity.

Although each column may be read by itself, there is a logical grouping to the complete set. Columns 1 through 5 form Part I of the book. They review programming fundamentals: problem definition, algorithms, data structures and program verification and testing. Part II is built around the theme of efficiency, which is sometimes important in itself and is always a fine springboard into interesting programming problems. Part III applies those techniques to several substantial problems in sorting, searching and strings.

One hint about reading the essays: don't go too fast. Read them carefully, one per sitting. Try the problems as they are posed -- some of them look easy until you've butted your head against them for an hour or two. Afterwards, work hard on the problems at the end of each column: most of what you learn from this book will come out the end of your pencil as you scribble down your solutions. If possible, discuss your ideas with friends and colleagues before peeking at the hints and solutions in the back of the book. The further reading at the end of each chapter isn't intended as a scholarly reference list; I've recommended some good books that are an important part of my personal library.

This book is written for programmers. I hope that the problems, hints, solutions, and further reading make it useful for individuals. The book has been used in classes including Algorithms, Program Verification and Software Engineering. The catalog of algorithms in Appendix 1 is a reference for practicing programmers, and also shows how the book can be integrated into classes on algorithms and data structures.

The Code
The pseudocode programs in the first edition of the book were all implemented, but I was the only person to see the real code. For this edition, I have rewritten all the old programs and written about the same amount of new code. The programs are available at this book's web site. The code includes much of the scaffolding for testing, debugging and timing the functions. The site also contains other relevant material. Because so much software is now available online, a new theme in this edition is how to evaluate and use software components.

The programs use a terse coding style: short variable names, few blank lines, and little or no error checking. This is inappropriate in large software projects, but it is useful to convey the key ideas of algorithms. Solution 5.1 gives more background on this style. The text includes a few real C and C++ programs, but most functions are expressed in a pseudocode that takes less space and avoids inelegant syntax. The notation for i = 0, n) iterates i from 0 through n-1. In these for loops, left and right parentheses denote open ranges (which do not include the end values), and left and right square brackets denote closed ranges (which do include the end values). The phrase function(i, j) still calls a function with parameters i and j, and arrayi, j still accesses an array element.

This edition reports the run times of many programs on ''my computer'', a 400MHz Pentium II with 128 megabytes of RAM running Windows NT 4.0. I timed the programs on several other machines, and the book reports the few substantial differences that I observed. All experiments used the highest available level of compiler optimization. I encourage you to time the programs on your machine; I bet that you'll find similar ratios of run times.

To Readers of the First Edition
I hope that your first response as you thumb through this edition of the book is, ''This sure looks familiar.'' A few minutes later, I hope that you'll observe, ''I've never seen that before.''

This version has the same focus as the first edition, but is set in a larger context. Computing has grown substantially in important areas such as databases, networking and user interfaces. Most programmers should be familiar users of such technologies. At the center of each of those areas, though, is a hard core of programming problems. Those programs remain the theme of this book. This edition of the book is a slightly larger fish in a much larger pond.

One section from old Column 4 on implementing binary search grew into new Column 5 on testing, debugging and timing. Old Column 11 grew and split into new Columns 12 (on the original problem) and 13 (on set representations). Old Column 13 described a spelling checker that ran in a 64-kilobyte address space; it has been deleted, but its heart lives on in Section 13.8. New Column 15 is about string problems. Many sections have been inserted into the old columns, and other sections were deleted along the way. With new problems, new solutions, and four new appendices, this edition of the book is 25 percent longer.

Many of the old case studies in this edition are unchanged, for their historical interest. A few old stories have been recast in modern terms.

Acknowledgments for the First Edition
I am grateful for much support from many people. The idea for a Communications of the ACM column was originally conceived by Peter Denning and Stuart Lynn. Peter worked diligently within ACM to make the column possible and recruited me for the job. ACM Headquarters staff, particularly Roz Steier and Nancy Adriance, have been very supportive as these columns were published in their original form. I am especially indebted to the ACM for encouraging publication of the columns in their present form, and to the many CACM readers who made this expanded version necessary and possible by their comments on the original columns.

Al Aho, Peter Denning, Mike Garey, David Johnson, Brian Kernighan, John Linderman, Doug McIlroy and Don Stanat have all read each column with great care, often under extreme time pressure. I am also grateful for the particularly helpful comments of Henry Baird, Bill Cleveland, David Gries, Eric Grosse, Lynn Jelinski, Steve Johnson, Bob Melville, Bob Martin, Arno Penzias, Marilyn Roper, Chris Van Wyk, Vic Vyssotsky and Pamela Zave. Al Aho, Andrew Hume, Brian Kernighan, Ravi Sethi, Laura Skinger and Bjarne Stroustrup provided invaluable help in bookmaking, and West Point cadets in EF 485 field tested the penultimate draft of the manuscript. Thanks, all.

Acknowledgments for the Second Edition
Dan Bentley, Russ Cox, Brian Kernighan, Mark Kernighan, John Linderman, Steve McConnell, Doug McIlroy, Rob Pike, Howard Trickey and Chris Van Wyk have all read this edition with great care. I am also grateful for the particularly helpful comments of Paul Abrahams, Glenda Childress, Eric Grosse, Ann Martin, Peter McIlroy, Peter Memishian, Sundar Narasimhan, Lisa Ricker, Dennis Ritchie, Ravi Sethi, Carol Smith, Tom Szymanski and Kentaro Toyama. I thank Peter Gordon and his colleagues at Addison-Wesley for their help in preparing this edition.

Updates

Errata

The second printing had no changes from the first printing.

The following bugs need to be fixed in upcoming printings:

p. 38, line 23. The clause cantbe(m, n) should be cantbe(m, n-1).

p. 121, line 11: The inequality sign is reversed; the test should read "if u-l < cutoff". (The test is correct in the function qsort4 later on the page.)

p. 129, line -14: The variables "m" and "n" are swapped. The sentence should read: "Next, suppose that m is ten million and n is 2³¹."

p. 181, line -6: Change "structues" to "structures".

p. 203, line 12: Change "commutative" to "associative".

p. 224, line -2: Remove the phrase "or print n + 1 - i rather than i".

p. 231, line -13: Insert "p" after "*", so the line reads

 unsigned int hash(char *p) 

Submit Errata