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

I originally bought this book as a source of remedial study following the end of my US state school CS undergrad experience (I completed a BS Computer Science in 2013, > 3.5 GPA), and as preparation for V1 & V4 of TAOCP. I use the word remedial here in the sense that I felt that I was missing a critical foundation in the mathematical analysis and derivation of algorithms, even after the course-work of that degree. I've done 3 chapters of it in full, and I will mention a number of things that other reviews haven't talked about. Due to the horrendous time commitment of this book, I strongly suspect this is because those reviewers haven't actually worked through it, and have instead chosen to skim and allow Knuth fanboyism, along with the desire for mutual association, to cloud their opinions. I'm revoking a star simply to balance those reviews out, and so that graduates in similar situations have an actual informed critical opinion of this book to find among the reviews.

Take-Aways (As of Ch 3):

There are many aspects of summations, integer functions, and proofing that: I never saw covered in my CS degree, are unforgettable, and can be immediately applied to most algorithm research. Those alone make this book worth every penny. Further, the problems posed by this book are more than just repeated mechanics, as I have seen in books like those mentioned below. Each problem is carefully chosen, thorough, and exposes multiple aspects of each topic. They really do weed out many faults that I wasn't really exposed to- as a small example: the importance of ensuring validity of n-1 and n-2 hypothesis & base cases during an induction proof.

The Bad:

Students educated through a contemporary CS track at most American uni's, I believe, (e.g. Rosen Discrete Math, Cormen Algorithms) will find this book both terrifyingly terse and frustratingly paced. In many cases, examples are given without derivation. In many cases, important points are made without obvious connection to previous topics. This is not without a solution however, and getting through this book is often an acquired technique of paper noting things as-you-go, as well as a learned hyper-literacy. The terseness is also a double-edged sword, as sometimes I found it useful as an extra opportunity to practice the taught methods to see if I could come to the same result. Further, the reader should be prepared to go back and review propositional logic & university calculus theorems (atleast FTC, definite vs indefinite integrals). For example, the description of sum by parts in the section on finite calculus assumes _much_ from the reader, and being able to use university calc. as a point of reference to get through that is helpful.

A lot of exercises are tersely explained in both problem and solution. Further, many solutions are totally left-field (having little to do with material in the book). This isn't necessarily bad, as even taking the wrong path to a solution is very educational. However, at some point the reader has to make a judgment as to how long to commit to a certain problem. Many terse problems & left-field solutions instill the wrong judgment: quitting too early.

Conclusion:

Attention to detail & extra work is necessary to overcome the terseness of this particular beast, but it's worth it. I recommend this book for developers confronted with algorithm optimization problems, as a well as for a different take on parts of discrete math, and definitely for students coming out of a US state school CS program, the last which this book complements very well. Having worked through some of V1 TAOCP, I would also say that the book is effective in expanding upon its math underpinnings (V1 at-least), and incidentally, does give one confidence to tackle Knuth's other works.

This book is great. It is the funnest math book I have worked with, and I appreciate the intensity of the mathematics -- something that is falling out of the norm in computer science. The book is also a great source of fantastic combinatorics.

Development seems not too deep but problems and exercises make it an extremely interesting book.

I have the First Edition and came here to look into the Second Edition. There are several negative reviews and basically those folks have fundamental misunderstandings. So I'll add my review.

First, what kind of book is it? It is not an introductory-level math book with lots and lots of repetition. It is a book on hard math, done in a concise manner by brilliant teachers who assume students are very comfortable with calculus, probability, etc. You really cannot afford to skip around and dabble as if this were an introductory algebra course or something. (I'm not being elitist. I did not attend Stanford and don't consider myself a math genius and am not making this a "we versus the unwashed masses" issue, as I have really struggled with the material myself.)

Second, what is the book about? Several reviewers have theories on where the "Concrete" part of the title comes from, but the bottom line is that it's a book on the discrete math that you need to know for theoretical computer science. (For example, discrete calculus versus the continuous calculus we all learned in school.) Any Analysis of Algorithms course, for example, will confront you with recurrence equations and lots of discrete math.

Third, how is the book organized? At first, it appears rather disjoint. The authors have a sort of, "Hey, look at that flower," and "hey, look under this rock" kind of approach as you walk down a path but the path itself isn't really spelled out. None-the-less, the book does build step-by-step from examples of recurrence equations (Towers of Hanooi, Josephus) in Chapter 1, to Generating Functions in Chapter 7.

Perhaps they could have made the path more explicit, but I can't see how they'd organize it much differently. They could throw entire chapters into Appendices, but things build on each other in such a way that you'd simply have to skip around from the main chapters to the Appendix anyhow.

Fourth, what other books cover this material? I'm not well-qualified to talk about the entire universe of books, but I must say that the three Analysis of Algorithm books I have for my current class definitely give only the very basics of this material and really only present two possibilities: 1) fiddle around with the equation, possibly using a graphic representation, until you see a pattern and make a guess, then prove it by induction, or 2) if your algorithm is one specific class, plug some numbers into this 3-part formula and if one of the parts applies an answer will pop out for you. Concrete Math is gives you many powerful tools to solve such problems.

Fifth, what is the flavor of the book? The authors have an informal writing style -- outside of the very formal math and proofs -- and the book has marginal notes that were contributed by the "beta-tester students" as the book was being written.

Some reviewers have criticized the marginal notes, and I simply have to shake my head and be glad I don't have to work alongside them. Yes, many of the notes are puns or other humor, but those are a nice break from the heavy math. And many of the notes provide great hints and perspectives from students who are also learning the material. I wish all technical books had such notes, but only a Knuth could get a publisher to go to the trouble.

So that's my review. An excellent book that's very intense and covers a hard, very technical topic. It's like learning math from algebra to differential equations all over again in a different language, and perhaps the negative reviewers simply never understood this. If you're not a programmer who needs to rigorously analyze algorithms, skip the book unless you simply want to learn for the joy of learning.