Customer Reviews

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

5 star:		(21)
4 star:		(9)
3 star:		(1)
2 star:		(1)
1 star:		(1)

 

 

What is "concrete" math, as opposed to other types of math? The authors explain that the title comes from the blending of CONtinuous and disCRETE math, two branches of math that many seem to like to keep asunder, though each occurs in the foundation of the other. The topics in the book, such as sums, generating functions, and number theory, are actually standard discrete math topics; however, the treatment in this text shows the inherent continuous (read: calculus) undergirding of the topics. Without calculus, generating functions would not have come to mind and their tremendous power could not be put to use in figuring out series.

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.

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".

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.

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.

This book is great. But many excercises are too hard for non-mathematically trained reader. I can solve almost all warm-up exercises without peeking the answer. But even few warm-up excercises are virtually research one. For example, see the exercise 2.1. The answer for this exercise is that there is no agreement about this. I think it means that there is no answer for this exercise. Sometimes even understanding an answer is very hard when you read an answer because you can't solve an exercise. This book contains answers for all exercises. But this book's exercises are MUCH HARDER than many other mathematic books which contain answers for only odd number(or even number) exercises.
You need a great inductive mathematical reasoning experience to read this book. If you finish this, you can omit the first 100 pages of TAOCP vol 1.
It would be nice if there is a solution book for this hard concrete book.

Why I got this book:
It's a great feeling to know how computers work, when I decided that I want to make a career and a life out of computers, as its truly a passion for me, I delved deeper, discovering the true beauty in the Science part of Computer Science, so I decided to get Donald Knuth' "The Art of Computer Programming" - to describe that seminal, huge work, it's like biting more than you can chew while trying to drink from a fire hose, moreover, the technical and mathematical prerequisites for the work are sometimes too demanding, they require a huge amount of experience with discrete mathematics, although I had some lectures and read some books, none came close "Concrete Mathematics", it covers, from ground up (though with a dangerously steep learning curve) a lot of discrete mathematics topics, it is by far the most extensive work I've read about Sums and really teaches the algorithmic problem solving thinking skill the authors preach so much about, with small amusing comments written by actual students of this course, a comfortable format, and very good writing skills, you can feel these guys are great professors who enjoy this material and are passionate about teaching it.

Recommended, though some better, less steep, introductionary text books are probably out there.

Enjoy.

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.

I used this book while studying Combinatorics at the University of Warwick, a leading British institution for mathematicians. At the time, the book was a little bit overwhelming - Knuth doesn't waste any time in getting to the point of solving problems in the book. Thus, if you're the type of person who needs lots of worked examples, I would supplement this with another book, for example, Grimaldi's Discrete and Combinatorial Mathematics. But this book does belong on the bookshelf - it is a great reference, particularly because it prepares one to read The Art of Computer Programming, also by Knuth. TAOCP is the definitive series on computer science, respected by computer scientists everywhere. I guess the best way to describe Concrete Mathematics is that if you are a graduate student in CS, you should own this book. If you are a mathematically-oriented undergraduate, this book will make you really understand anything that your professors will throw at you. But, if you are not a math-lover, you will want a backup and a really nice professor :)

This book's title can be misleading. I would say it is more of an advanced textbook on the mathematics that is a foundation for computer science than a foundational book on the mathematics of computer science. I think this misreading of the title and thus the book's content is what is behind much of the heartache that readers have when trying to tackle it. This book expands on the "Mathematical Preliminaries" portion of "The Art of Computer Programming" series of books by Knuth, and thus this book has a style much like that series of books. The book is complete and clear, but it is also densely packed with lots of theory and proofs and will require much effort and time to understand well. It is really not meant to be an applied mathematics textbook at all. I show the table of contents next. Note that there are exercises at the conclusion of each chapter with solutions in the back of the book. However, most of the exercises are not so simple that you can just glimpse at the solution and figure out how to get from A to B. I recommend it if you have the time. It can really bring out thoughts and the beauty of mathematics that you may not have considered before.

1. Recurrent Problems.
The Tower of Hanoi.
Lines in the Plane.
The Josephus Problem.
Exercises.

2. Sums.
Notation.
Sums and Recurrences.
Manipulation of Sums.
Multiple Sums.
General Methods.
Finite and Infinite Calculus.
Infinite Sums.
Exercises.

3. Integer Functions.
Floors and Ceilings.
Floor/Ceiling Applications.
Floor/Ceiling Recurrences.
'mod': The Binary Operation.
Floor/Ceiling Sums.
Exercises.

4. Number Theory.
Divisibility.
Factorial Factors.
Relative Primality.
'mod': The Congruence Relation.
Independent Residues.
Additional Applications.
Phi and Mu.
Exercises.

5. Binomial Coefficients.
Basic Identities.
Basic Practice.
Tricks of the Trade.
Generating Functions.
Hypergeometric Functions.
Hypergeometric Transformations.
Partial Hypergeometric Sums.
Mechanical Summation.
Exercises.

6. Special Numbers.
Stirling Numbers.
Eulerian Numbers.
Harmonic Numbers.
Harmonic Summation.
Bernoulli Numbers.
Fibonacci Numbers.
Continuants.
Exercises.

7. Generating Functions.
Domino Theory and Change.
Basic Maneuvers.
Solving Recurrences.
Special Generating Functions.
Convolutions.
Exponential Generating Functions.
Dirichlet Generating Functions.
Exercises.

8. Discrete Probability.
Definitions.
Mean and Variance.
Probability Generating Functions.
Flipping Coins.
Hashing.
Exercises.

9. Asymptotics.
A Hierarchy.
O Notation.
O Manipulation.
Two Asymptotic Tricks.
Euler's Summation Formula.
Final Summations.
Exercises.

A. Answers to Exercises.
B. Bibliography.

I had the pleasure of taking the course "Concrete Mathematics" with Ron Graham as an undergrad engineering student at Princeton University in the late 1980s, and in retrospect it was quite possibly the highlight of my academic career. Likewise, this text has a cherished spot in my bookcase even to this day. The material is challenging, sometimes downright frustrating, but good stuff nonetheless... and as others have noted, very useful! The skills gained are specifically tailored for application in fields such as computer science, really a number of disciplines; and complement what one learns in the more "standard" math courses. How many academic texts have become must-haves even beyond your college years? For me, only this one. I'd give it fifteen stars if I could.