I just spent the evening filling two boxes with books I’ll bring from Québec to my new apartment in New York. To my surprise and delight, that’s less than a third of my collection (plus newer ones I have yet to make my mind about). Perhaps this list of books that survived the cull can guide others in their acquisitions. If you’re around NYC, I’d also be very happy to share my stash!

EDIT: I was asked for feedback on some of these books, so I added some inline.

Fundamentals

Brassard and Bratley, Fundamentals of Algorithmics is my go-to reference book for basic algorithmic stuff. I love the presentation, the authors are careful with Landau notation, and they specify in what circumstances hand-waving tricks apply. The quality of Brassard’s lectures is probably a factor as well: the book reminds me of one of the best courses in Université de Montréal’s undergraduate curriculum.

CLRS for baseline implementations of classic data structures and algorithms.

Knuth 1-4A for its attention to minutiae. Also very useful as a reference to point to: if something is so old or well known that I can’t think of a canonical reference, it’s probably in Knuth.

Sedgewick, Algorithms (First edition) has an interesting section on geometric algorithms. I also like the way many older data structure and algorithm books clearly take low-level coding consideration into account while discussing asymptotics. I find nearly everything by Tarjan very good in that regard; his papers are among the few that describe (and painstakingly prove) algorithmic improvements (e.g., the inverse-Ackermann Union Find) only to reveal that a simpler implementation with a worse bound consistently performs better in practice.

Correctness

Bertot and Castéran, Interactive Theorem Proving and Program Development is heavy and I’m still going through the book.

Pierce, Types and Programming Languages should be mandatory skimming before entering a debate on “static” and “dynamic” types.

Gries, The Science of Programming changed the way I write programs. It’s not that I go full formal on my code, but that I try and structure it so it’s easier to reason about. I was just reminded of Dijkstra’s Discipline of Programming. The first time I read both books, I did so concurrently. It was a long time ago, and I was less mature mathematically, but I definitely remember finding Gries clearer and more directly applicable, while Dijkstra did a better job of making me think hard about how to best express the meaning of code. Even now, I’d say they’re still complementary.

Jackson, Software Abstraction describes an interesting approach to interpolate between testing and formal methods. This book changed the way I write tests. It’s also based on a nice application of combinatorial optimisation ;)

Oram and Wilson, Beautiful Code feels uneven to me. Some chapters cover inspiring gems, but many left no mark. A friend suggests Bentley’s Programming Pearls or Neuman’s Computer Related Risks.

Performance

Golub and Van Loan, Matrix Computations is obviously a good reference for the implementation of dense linear algebra. However, I like this work even more for its clear and precise discussion of performance and numerical precision matters. One can’t hide behind big-Oh when discussing linear algebra. Yet, the book is as enlightening and general as classic tomes on asymptotic analysis of algorithms and data structures. Better: that is true for both the implementation and the use of the algorithms they describe. If all software engineering were as well understood as numerical linear algebra, our discipline would be in a good place.

McGeoch, A Guide to Experimental Algorithmics was my bedside companion for the holiday season. On several occasions, I told friends that this is the book I wish I had read ten years ago and that I dreamt of writing the past couple year. It has good rules of thumb and suggestions for everything from designing proper experiments to deriving robust performance models.

Warren, Hacker’s Delight is really a fundamental book for me. It’s not that bit twiddling tricks are that important, but that I know I can count on Warren’s nice exposition if I need to direct someone to a reference. Now nicely complemented by Knuth 4A.

Operations research

Continuous optimisation

Ahuja, Magnanti and Orlin, Network Flows because it describes all the classics. In particular, if an optimisation problem is in P, it’s probably in there.

Bazaraa, Sherali and Shetty, Nonlinear Programming mostly for a couple convergence proofs and as a reference.

Chvátal, Linear Programming for its unique (? rare, definitely) and insightful presentation of linear optimisation and of classic duality theorems. I like the sections on Network flows and on Basis factorisation for similar reasons.

Hiriart-Urruty and Lemaréchal, Convex Analysis and Minimization Algorithms because decomposition methods depend on convex nondifferentiable optimisation. I rarely care about general convex optimisation, but it’s an unavoidable building block for Lagrangian decomposition methods.

Combinatorial optimisation

Bollobás, Modern Graph Theory mostly as a reference for classic results. I remember having a lot of fun with the section on matchings.

Lawler, Combinatorial Optimization is short but dense. I don’t grok matroids, and someone I respect gave me this book and told me it would all make sense once I’d gone through it.

Nemhauser and Wolsey, Integer and Combinatorial Optimization for the dark times when I need to directly think in terms of polytopes and facets, or when I try to generate fancy cuts.

Schrijver, Combinatorial Optimization mostly as a reference for theoretical results. It’s exhaustive, so I can use it like the TAoCP of optimisation and as a springboard to other work.

Wolsey, Integer programming when Nemhauser is hard to follow.

Messy stuff

These books help me approach problems that don’t fit neatly in any box.

Bertsekas, Dynamic Programming and Optimal Control and Law, Simulation, Modeling and Analysis fill holes left by my focusing on deterministic single-period problems. I use Bertsekas and Law as refreshers when I remember that I’m forgetting something. I can then decide whether to go more deeply in that direction.

Polya, How to Solve It. For the really dark times when it feels like I’m asked to do the impossible. Perhaps it’s mostly useful because it distracts me from the immediate task for a couple minutes. Either way, I like to re-read it when I get stuck.

Tufte, The Visual Display of Quantitative Information, along with Hadley Wickham’s ggplot2, taught me to think deliberately about presenting results. Our visual cortex is pretty awesome but bad visualisation wastes our brain on distractions.