Programming Pearls, 
           Second Edition
     by Jon Bentley. 
     Addison-Wesley, Inc., 2000. 
     ISBN 0-201-65788-0. 
     239 + xi pp.   $24.95 
     This book is a collection of essays about a glamorous aspect of 
     software: programming pearls whose origins lie beyond solid 
     engineering, in the realm of insight and creativity. This book 
     provides a guide for both students and experienced 
     programmers about how to design and create programs, and 
     how to think about programming. 
     The book is full of small case studies, real examples, and interesting exercises for learning about how to program. 
     This web page contains samples from the whole work for you to investigate. For teachers, the links below lead to 
     some of the central material suitable for classroom use. 
     Steve McConnell describes the book as ``a celebration of design in the small''. Browse this site to sample it 
     yourself. 
        What's new on this web site? 
     From The Book 
     Table of Contents 
     Preface 
     Part I: Preliminaries 
       Column 1: Cracking the Oyster 
       Column 2: Aha! Algorithms [Sketch] 
       Column 4: Writing Correct Programs [Sketch] 
       Column 5: A Small Matter of Programming [Sketch] 
     Part II: Performance 
       Column 7: The Back of the Envelope 
       Column 8: Algorithm Design Techniques [Sketch] 
     Part III: The Product 
       Column 14: Heaps [Sketch] 
     Column 15: Strings of Pearls 
       
     Epilog to the First Edition 
     Epilog to the Second Edition 
     Appendix 2: An Estimation Quiz 
     Appendix 3: Cost Models for Time and Space 
          Appendix 4: Rules for Code Tuning 
          Solutions for Column 1   Column 5   Column 7   Column 15 
          Index 
          About The Book 
          Why a Second Edition? 
          To Readers of the First Edition 
          About the First Edition 
          Errata 
          Supporting Material 
          Source Code 
          Web Sites Relevant to the Book 
          Animation of Sorting Algorithms 
          Tricks of the Trade 
          Teaching Material 
          Other Links 
                 ●     Addison-Wesley Computer & Engineering Publishing Group 
                 ●     Programming Pearls at Addison-Wesley 
                 ●     Bookstores: Amazon.com, Barnes & Noble, Borders.com, Fatbrain.com, Quantum Books. 
          Copyright © 1999 Lucent Technologies. All rights reserved. Thu 19 Oct 2000 
       What's New on the 
       Programming Pearls 
       Web Site
       November 2000
       Column 15 is now on the site, complete with a new program for 
       letter-level Markov text, and new examples of word 
       frequencies, long repeated strings, and letter-level and word-
       level Markov text. 
       October 2000
       The rules for code tuning from my 1982 book Writing Efficient Programs are now online, and so is a Powerpoint 
       Show on Cache-Conscious Algorithms and Data Structures. 
       August 2000
       The errata just keeps on growing. If you see errors, please send them in. 
       July 2000
       Programming Pearls is often used for teaching undergraduates. This page describes how some of the topics in the 
       book can be incorporated into college classrooms. 
       March 2000
       A theme running through the book concerns the Tricks of the Trade. This page describes that topic and contains a 
       Powerpoint Show on the subject. 
       Copyright © 1999 Lucent Technologies. All rights reserved. Mon 6 Nov 2000 
    Strings of Pearls 
    (Column 15 of 
    Programming Pearls) 
    We are surrounded by strings. Strings of bits make integers and 
    floating-point numbers. Strings of digits make telephone 
    numbers, and strings of characters make words. Long strings of 
    characters make web pages, and longer strings yet make books. 
    Extremely long strings represented by the letters A, C, G and T 
    are in geneticists' databases and deep inside the cells of many 
    readers of this book. 
    Programs perform a dazzling variety of operations on such 
    strings. They sort them, count them, search them, and analyze 
    them to discern patterns. This column introduces those topics by examining a few classic problems on strings. 
    The Rest of the Column
    These are the remaining sections in the column. 
    15.1 Words 
    15.2 Phrases 
    15.3 Generating Text 
    15.4 Principles 
    15.5 Problems 
    15.6 Further Reading 
    Related Content
    The teaching material contains overhead transparencies based on Sections 15.2 and 15.3; the slides are available in 
    both Postscript and Acrobat. 
    The code for Column 15 contains implementations of the algorithms. 
    The Solutions to Column 15 give answers for some of the Problems. 
    This column concentrates on programming techniques, and uses those techniques to build several programs for 
    processing large text files. A few examples of the programs' output in the text illustrate the structure of English 
    documents. This web site contains some additional fun examples, which may give further insight into the structure 
    of the English language. Section 15.1 counts the words in one document; here are more examples of word 
    frequency counts. Section 15.2 searches for large portions of duplicated text; here are more examples of long 
    repeated strings. Section 15.3 describes randomly generated Markov text; these pages contain addtional examples 
    of Markov text, generated at the letter level and word level.