Concrete Mathematics: A Foundation for Computer Science (2nd Edition)

The smart-aleck marginal notes notwithstanding, this is a serious math book for those who are willing to dot every i and cross every t. Unlike most math texts (esp. graduate math texts), nothing is omitted along the way. Notation is explained (=very= important), common pitfalls are pointed out (as opposed to the usual way students come across them -- by getting back bleeding exams), and what is important and what is =not= as important are indicated.

Still, I cannot leave the marginal notes unremarked; some are serious warnings to the reader. For example, in the introduction, one note remarks "I would advise the casual student to stay away from this course." Notes that advise one to skim, and there are a few, should be taken seriously. All the marginal notes come from the TAs who had to help with the text, and thus have a more nitty-gritty understanding of the difficulties students are likely to face. Still, there are plenty of puns and bad jokes to amuse the text-reader for hours: "The empty set is pointless," "But not Imbesselian," and "John .316" made me chuckle, but you have to find them for yourself.

To someone who has been through the rigors of math grad school, this book is a delight to read; to those who have not, they must keep in mind that this is a serious text and must be prepared to do some real work. Very bright high school students have gotten through this text with little difficulty. I want to note ahead of time - some of the questions in the book are serious research topics. They don't necessarily tell you that when they give you the problem; if you've worked on the problem for a week, you should turn to the answers in the back to check that there really is a solution.

That said, I would highly recommend this book to math-lovers who want some rigorous math outside of the usual fare. The formulas in here can actually come in handy "in real life", especially if one has to use math a lot.


Useful and well-written   January 31, 2000
Naomi Novik (New York, NY USA)
45 out of 47 found this review helpful

This is one of those books you keep forever, purely for its utility: it's packed with formulas, techniques, examples. But more than that, the authors lead you through the techniques and explain the concepts behind them, with the goal of equipping you with the mental tools to attack any mathematical problem you encounter. And to top it off, it's well-written, and the "margin notes" provide some comic relief. The material is very dense, and it's not a book I'd recommend for casual reading: this is stuff you only work through if you're going to need it. But if you *are* going to need it, this book will make it a lot more pleasant.


Beware of great books   October 4, 2005
James Street (Oakland, CA USA)
66 out of 67 found this review helpful

This book is excellent (5 stars) if you have the mathematical "maturity" that it assumes. If not, it will vary from 4 stars to 0 stars.

The problem is, the book looks as if it might be an entry level text and it is tempting to think that with a little extra hard work any intelligent, reasonably well-grounded mathematics undergraduate student could prove that he is a genius by mastering the content. A fair number, of course, will do just that. But many more will unnecessarily bloody their noses and egos.

Most people skip prefaces but this one shouldn't be skipped. The preface says that most of the people who have taken the course that the book is based on have been graduate students and alumni and (some) have been juniors and seniors.

To give an example of the difficulty an unwary student might find: The chapter on probability looks straightforward and well-written and it is! But it is truly useful only to students who have already studied probability theory and mastered the basic theory. The trap is that the book does, in fact, provide introductions to most of the topics covered. But in reality, they are reviews, introductions to the symbols and notation to be used and repositories for results that will be referenced throughout the book.

The prerequisites for having a profitable encounter with this book are : a good understanding of elementary number theory, probability theory and linear algebra and two years of calculus with a very good understanding of infinite series. A good knowledge of generating functions and recursive functions is also necessary. A few juniors and seniors will always be dedicated and smart enough to achieve this level of maturity but it usually takes more than four years.

In addition, while any reasonably intelligent mathematics student can learn the topics covered in this book, it is written by three master programmers and discrete mathematicians and inevitably also contains enough to challenge just about anyone (even them.) After all, the book is dedicated to Leonard Euler, possibly implying that the authors think he is among the very few persons who could have solved most (all?) of the problems.


I wish every book were written like this!   December 14, 2005
Anthony Widjaja To (Toronto, ON Canada)
26 out of 26 found this review helpful

This book is perhaps one of the most beautifully written books I have ever read. All the proofs presented here are elegant. When reading the proofs in this book, you can feel that one sentence logically and smoothly follows from the previous sentence. This is partly because of the elegant and effective notations adopted by the authors. [Note: Donald Knuth, one of the authors, has been one of the biggest proponents of good mathematical notations. See his book titled "Mathematical Writing".]

Other reviewers have provided a summary of this book. So, I will only say that every computer scientist and combinatorialist should read at least chapters 1, 2, 5, 7, and 9. Chapter 5 is very highly recommended. Trust me: once you have mastered these chapters, you will be able to do things your colleagues just can't. Even just familiarizing yourself with the notations in this book will help you produce proofs that you probably won't be able to otherwise. [Great ideas are of course always important in every proof - but without good notations, you probably won't be able to come up with the ideas in the first place.]

There is pretty much nothing bad about this book that I am aware of. I will just say though that it takes a lot of time and effort to acquire mastery of the material. As for my own story, I started reading chapter 1 and 2 when I just got interested in discrete mathematics. It took me about 1/2 year (part time) to get through this. I came back to this book again when I took a course on "generatingfunctionology". I found that chapter 5 and 7 were indispensable. I was also forced to reread chapter 2 again because the lecturer, as most people do, just waived his hands when it comes to manipulating sums and binomial coefficients. However, all the effort that I put in paid off in the end as I could solve problems in the final exam which all my other friends could not.

In summary, I strongly recommend this book to every computer scientist and combinatorialist. I will finally remark that, if you are serious about learning concrete mathematics, you will probably find that generating functions pop up pretty much everywhere. To understand these beasts, I highly recommend Sedgewick and Flajolet's "Introduction to Analysis of Algorithms" and "Analytic Combinatorics" (not yet published, but next-to-final draft is available at Flajolet's web site), and Wilf's "Generatingfunctionology".


Concrete Math--neither "abstract" nor "applied"   May 15, 2001
M. Le Brun (Novato, CA USA)
23 out of 27 found this review helpful

Lest others find this wonderful book as disappointing as the reviewer from Osan, Korea: note that "concrete" in the title is just meant in contrast to "abstract". But both concrete and abstract are adjectives intended only to describe different apporaches to *theoretical* math, as opposed to *applied* math, which addresses examples directly relevant to the real world (and thus is probably of more interest to engineers and their ilk). This *isn't* an applied math text. The difference between the concrete and abstract styles is that concrete math generally takes a "bottom up" tack, arising from specific given "concrete" entities, such as certain special functions, sums, sequences etc and tends to involve more derivation and calculation. In contrast typical abstract math is more "top down", proceeding, say, from axioms, perhaps even non-constructively, and tends to involve more reasoning and proving. If you dig the theoretical stuff, and like the concrete approach, this book is a treasure trove.