The Art of Computer Programming. Donald E. Knuth. Addison-Wesley, 1997/2011.

Often cited, but rarely read. It’s really a shame, for these books are incredibly rich. Numerous jewels are hidden everywhere, sometimes inside exercise solutions (and there are many exercises). It is dense, obviously, and it may take a lot of time to digest a single page. But you will never waste your time doing this. Those who stop at the presence of assembly code are missing the point.

Algorithms, 4th Edition. Robert Sedgewick, Kevin Wayne. Addison-Wesley, 2011.

For me, the best book on algorithms. Beautiful figures and numerous examples. Crystal clear Java code. (The choice of Java for such a book is convincing.) The companion web site provides code, data, and lecture slides.

Note: this is the 4th edition; this is important.

The Practice of Programming. Brian W. Kernighan, Rob Pike. Addison-Wesley, 1999.

This book is worth buying, even if only for the last three pages, where the programming rules discussed in the book are collected. We should have the students learn these rules by heart; we should apply these rules ourselves. This book provides an outstanding insight on programming.

There is an implicit message: the choice of programming language is not as important as one may think.

Computer Systems: A Programmer’s Perspective. Randal E. Bryant, David R. O’Hallaron. Pearson, 2011.

Everything programmers should know about hardware, system, compiler, etc., to improve their skills. Likely to be the only book where a whole chapter is devoted to linking.

Written by programmers, for programmers.

Purely Functional Data Structures. Chris Okasaki. Cambridge University Press, 1998.

First, a book that beautifully explains what are purely functional data structures, their interest, their implementation, and their complexity analysis, notably in presence of amortization and lazy evaluation. Tons of data structures, some being revisited with a lot of elegance. An example: binomial heaps. Crystal clear SML code, explained line by line.

Programming Pearls. Jon Bentley. Addison-Wesley, 1986.

Still relevant, more than thirty years later. Plenty of good advice. Perfect style, and perfect examples. Some chapters I liked a lot: Writing Correct Programs, The Back of the Envelope, Sorting, and Heaps.

As written in the preface: ``This book is written for programmers’’.

Hacker’s Delight. Henry S. Warren. Addison-Wesley, 2003.

Tons of arithmetic hacks, all delightful. Some are for fun only (and thus worth reading), but many are genuinely useful. For instance, this book tells you what your compiler is doing when your code divides by a constant.

The web site does not exist anymore, but is archived here.

Algorithms on Strings, Trees, and Sequences. Dan Gusfield. Cambridge University Press, 1997.

Mostly a book on text algorithms, with numerous algorithms beautifully explained (and proved!). There is a whole part on suffix trees, and notably an excellent explanation of Ukkonen algorithm (notoriously difficult to understand and to code). Also contains many applications of these algorithms.

The Elements of Computing Systems. Noam Nisan, Shimon Schocken. MIT Press, 2008.

The best way to understand everything is probably to build everything by oneself. That’s what is proposed in this book, where the reader is invited to build a machine, an assembler, a compiler, and finally an operating system. (Interpreters are provided.) Even if you do not undertake such a construction, the book is worth reading, preferably in one shot.

Companion web site: www.nand2tetris.org