122 of 122 people found the following review helpful
on June 20, 2007
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.
259 of 268 people found the following review helpful
on July 13, 2001
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.
221 of 229 people found the following review helpful
on October 3, 2005
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.
76 of 76 people found the following review helpful
on December 13, 2005
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".
71 of 74 people found the following review helpful
on January 30, 2000
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.
44 of 45 people found the following review helpful
on May 16, 2011
This is by far my favorite math book. I was introduced to it in a Putnam preparation course and didn't buy it at first (seemed too over the top). I found it in the library and used the school's book for some assignments. After a few nights studying out of the book I went off and bought it for myself, (half price, what a steal!) Granted, the book isn't for everyone, but if you even a glint of interest in discrete mathematics, you should definitely pick this book up.
I have not yet worked by way through the whole book (I've only solidly covered a sixth of it, but I've referenced about three quarters of it over the course of owning it). Here's what I like the most about the book:
- Good density / readability trade-off. Some math books are dense to the point that each page should take you an hour or more to fully understand. This isn't THAT bad, but it is definitely denser than your first year calculus texts. If you're used to breezing through a chapter that covers 2-6 concepts followed by some practice problems, you're going to have to get used to slowing down and doing some serious re-reading. I would estimate that getting a good grasp of each chapter takes about 20 to 60 hours of work, depending on how strong you are with the material. This includes time for solving the problems at the end of the chapter. This may sound like a lot, but trust me when I say you will know all the tricks of the trade when you're finished.
- Intuitive approach. I find many texts will spend a lot of time walking through the material in a very linear fashion. In the sense that the organization of the material makes sense once you've absorbed it, but seems random and un-ordered as you learn it. This book is ordered very intuitively the first time you read it, in the sense that the ideas seem to flow where your mind does when you first pick up the material (does this make sense?) Most chapters open with a (refreshingly tough) problem and you are walked through the solution as you learn the techniques you need to solve it. You'll pick up some very powerful problem solving techniques as you read this book.
- Good depth. Instead of telling you how to manipulate certain classes of sums, the authors go deep into the powers at work behind the problems, as well as "tricks of the trade". Some of the sum manipulations I've learned in this book I have yet to see elsewhere, and they're very handy! For example, a type of "discrete calculus" is defined, which will let you find the closed form for the sum of integers (1 through n) to the power of k with remarkable ease (it uses stirling numbers, I'm sure you can find it on the net.)
What I don't like about it:
- Doesn't take a very deep plunge into number theory. Covers the basics very well, but wont get you into RSA.
- Does not blend in continuous mathematics as well as I'd hoped.
In short, this book covers basic topics in discrete math very well. After reading this book you will be extremely comfortable manipulating sums, discrete probabilities, and number theory. It also gives you a surprisingly in-depth look at discrete math you don't often encounter in your undergraduate courses, including:
- Floor / ceiling functions and manipulating them.
- Binomial coefficients (n choose k).
- Generating functions.
- Special numbers (stirling, fibonacci, harmonic, etc.)
- O-notation (this is where the computer science finally kicks in).
Do read this book if you are:
- A math undergraduate.
- Someone who enjoyed math but lost touch with it long ago.
- Someone raised on continuous mathematics (calculus, high school math, analysis) looking to diversify their thinking.
- Into prime numbers, fibonacci numbers, or curious mathematical patterns.
Don't bother with this book if you are:
- A math genius.
- A computer whiz but don't enjoy math (despite the "foundation for computer science" line, this is purely a math book).
- An engineering student who only cares about the answer, not the process (see the one star guy).
- Note: This book doesn't use the lemma - proof - example format you may be used to. You've been warned.
This book is extremely well written, and I guarantee that if you're in the "read this book if" list you will find this book impossible to get rid of, it will haunt your bookshelf for life.
Also, concerning the title. There seems to be some confusion as to why it is called "Concrete Mathematics" (see one star guy). It isn't called that because it presents, everyday, formula-solution math. The reason it's called "Concrete Mathematics" (and I quote from the preface) is because "It is a blend of CONtinuous and disCRETE mathematics." That's by far the silliest book-title formula I've ever encountered, but to each their own I guess.
And finally, I didn't see a table of contents on the order page, so I will summarize the table of contents here, in order the topics are presented:
- Integer Functions (floor, ceiling, modulo)
- Number Theory
- Binomial Coefficients (n choose k)
- Special Numbers (Stirling, Eularian, Bernoulli, Fibonacci, and others)
- Generating Functions
- Discrete Probability
- Asymptotics (O notation)
There's just under 500 pages of good stuff before you hit the answer to exercises. Oh yeah, there's also no flimsy "answer to odd number exercises" back page. Each problem is solved ENTIRELY, some solutions take over a page. If that's not the best way to learn, I don't know what is. Enjoy.
28 of 30 people found the following review helpful
on September 20, 2004
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.
20 of 21 people found the following review helpful
on July 29, 2002
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.
27 of 30 people found the following review helpful
on May 15, 2001
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.
20 of 22 people found the following review helpful
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.
Sums and Recurrences.
Manipulation of Sums.
Finite and Infinite Calculus.
3. Integer Functions.
Floors and Ceilings.
'mod': The Binary Operation.
4. Number Theory.
'mod': The Congruence Relation.
Phi and Mu.
5. Binomial Coefficients.
Tricks of the Trade.
Partial Hypergeometric Sums.
6. Special Numbers.
7. Generating Functions.
Domino Theory and Change.
Special Generating Functions.
Exponential Generating Functions.
Dirichlet Generating Functions.
8. Discrete Probability.
Mean and Variance.
Probability Generating Functions.
Two Asymptotic Tricks.
Euler's Summation Formula.
A. Answers to Exercises.