book cover

First-Year Instruction
in Programming Pearls

Owen Astrachan organized a Workshop on First Year Instruction sponsored by the National Science Foundation and the Duke University Computer Science Department in July, 2000. When he invited me to give the keynote, my first response was that I haven't taught a freshman course for a quarter of a century.

On the other hand, I've enjoyed talking to undergraduates over the years, and Programming Pearls has been widely used as a supplementary text in college courses. My interest in the topic was also increased because my son was heading off to college later that summer. With Owen's guidance and encouragement, I agreed to talk on ``Truth, Beauty, and Engineering: What I'd Like My CS Freshman Kid to Learn Next Year''. (Let me clarify as a proud parent that Computer Science was only one of several possible majors that he was considering as he departed; I have high hopes that he can avoid repeating the sins of his father.)

The talk is available as a Powerpoint Show. It has this rough outline:
    Engineering
        Tricks of the Trade
        Eyes Open to the World
    Beauty
        Elegance
        Communication
    Truth
        History
        Ethics
Several of these topics are covered in the book.

Tricks of the Trade

This topic has its own web page, complete with a talk.

Elegance

Elegance is the moral of Column 1, and a theme through the rest of the book, complete with its own entry in the index. For a more general view of the topic, see the Computerworld article on Elegance in software.

I had the luxury of striving for elegance in the source code for the book. The scaffolding is often (appropriately) rough, but I took same pains to trim excess fat from most of the code that found its way into the text.

History

The book is peppered with little historical anecdotes that illustrate timeless truths. Section 10.1 introduces the topic of ``squeezing space'' with this story from the dawn of computing:

``Fred Brooks observed the power of simplification when he wrote a payroll program for a national company in the mid 1950's. The bottleneck of the program was the representation of the Kentucky state income tax. The tax was specified in the law by a two-dimensional table with income as one dimension, and number of exemptions as the other. Storing the table explicitly required thousands of words of memory, more than the capacity of the machine.

``The first approach Brooks tried was to fit a mathematical function through the tax table, but it was so jagged that no simple function would come close. Knowing that it was made by legislators with no predisposition to crazy mathematical functions, Brooks consulted the minutes of the Kentucky legislature to see what arguments had led to the bizarre table. He found that the Kentucky tax was a simple function of the income that remained after federal tax was deducted. His program therefore calculated federal tax from existing tables, and then used the remaining income and a table of just a few dozen words of memory to find the Kentucky tax.

``By studying the context in which the problem arose, Brooks was able to replace the original problem to be solved with a simpler problem. While the original problem appeared to require thousands of words of data space, the modified problem was solved with a negligible amount of memory.''

I tried to sprinkle such historical nuggets throughout the book. From the 1960's, Sections 2.4 and 2.8 describe a program for computing anagrams, and Section 9.3 describes a svelte binary search. From the 1970's, Problem 2.6 describes a touch-tone phone directory, Column 8 describes the evolution of an algorithm, Section 10.3 describes storing symmetric matrices, and Section 15.2 describes suffix arrays.

Copyright © 2000 Lucent Technologies. All rights reserved. Mon 3 Jul 2000