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

~ Ronald L. Graham (Author), (Author), (Author)

Editorial Reviews

Product Description

This book, updated and improved, introduces the mathematics that support advanced computer programming and the analysis of algorithms. The book's primary aim is to provide a solid and relevant base of mathematical skills. It is an indispensable text and reference for computer scientists and serious programmers in virtually every discipline.

From the Back Cover

This book introduces the mathematics that supports advanced computer programming and the analysis of algorithms. The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills - the skills needed to solve complex problems, to evaluate horrendous sums, and to discover subtle patterns in data. It is an indispensable text and reference not only for computer scientists - the authors themselves rely heavily on it! - but for serious users of mathematics in virtually every discipline.

Concrete Mathematics is a blending of CONtinuous and disCRETE mathematics. "More concretely," the authors explain, "it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems." The subject matter is primarily an expansion of the Mathematical Preliminaries section in Knuth's classic Art of Computer Programming, but the style of presentation is more leisurely, and individual topics are covered more deeply. Several new topics have been added, and the most significant ideas have been traced to their historical roots. The book includes more than 500 exercises, divided into six categories. Complete answers are provided for all exercises, except research problems, making the book particularly valuable for self-study.

Major topics include:

• Sums
• Recurrences
• Integer functions
• Elementary number theory
• Binomial coefficients
• Generating functions
• Discrete probability
• Asymptotic methods

This second edition includes important new material about mechanical summation. In response to the widespread use of the first edition as a reference book, the bibliography and index have also been expanded, and additional nontrivial improvements can be found on almost every page. Readers will appreciate the informal style of Concrete Mathematics. Particularly enjoyable are the marginal graffiti contributed by students who have taken courses based on this material. The authors want to convey not only the importance of the techniques presented, but some of the fun in learning and using them.

See all Editorial Reviews

Product Details

• Hardcover: 672 pages
• Publisher: Addison-Wesley Professional; 2 edition (March 10, 1994)
• Language: English
• ISBN-10: 0201558025
• ISBN-13: 978-0201558029
• Product Dimensions: 9.3 x 7.5 x 1.7 inches
• Shipping Weight: 3 pounds (View shipping rates and policies)
• Average Customer Review: 4.4 out of 5 stars  See all reviews (30 customer reviews)
• Amazon.com Sales Rank: #23,716 in Books (See Bestsellers in Books)

  Popular in these categories: (What's this?)

  #35 in	Books > Computers & Internet > Programming > Algorithms
  #40 in	Books > Computers & Internet > Computer Science > Software Engineering > Information Systems

Customer Reviews

Most Helpful Customer Reviews

94 of 95 people found the following review helpful:

5.0 out of 5 stars Beware of great books, October 3, 2005

By	James Street "Street Writer" (Oakland, CA USA) - See all my reviews (REAL NAME)

This review is from: Concrete Mathematics: A Foundation for Computer Science (Hardcover)

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.

146 of 151 people found the following review helpful:

5.0 out of 5 stars Please Be Discrete, July 13, 2001

By	Mary P. Campbell "math geek" (Flushing, NY USA) - See all my reviews (REAL NAME)

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.

51 of 54 people found the following review helpful:

5.0 out of 5 stars Useful and well-written, January 30, 2000

By	Naomi Novik "writer" (New York, NY USA) - See all my reviews (REAL NAME)

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.