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

Ronald L. Graham (Author), Donald E. Knuth (Author), Oren Patashnik (Author)

Book Description

Publication Date: March 10, 1994 | ISBN-10: 0201558025 | ISBN-13: 978-0201558029 | Edition: 2

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. 0201558025B04062001

Editorial Reviews

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.

About the Author

Donald E. Knuth is known throughout the world for his pioneering work on algorithms and programming techniques, for his invention of the Tex and Metafont systems for computer typesetting, and for his prolific and influential writing. Professor Emeritus of The Art of Computer Programming at Stanford University, he currently devotes full time to the completion of these fascicles and the seven volumes to which they belong.

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.4 x 7.8 x 1.4 inches
• Shipping Weight: 3 pounds (View shipping rates and policies)
• Average Customer Review: 4.5 out of 5 stars  See all reviews (33 customer reviews)
• Amazon Best Sellers Rank: #23,680 in Books (See Top 100 in Books)
  • #42 in Books > Computers & Technology > Programming > Algorithms

More About the Author

Donald E. Knuth was born on January 10, 1938 in Milwaukee, Wisconsin. He studied mathematics as an undergraduate at Case Institute of Technology, where he also wrote software at the Computing Center. The Case faculty took the unprecedented step of awarding him a Master's degree together with the B.S. he received in 1960. After graduate studies at California Institute of Technology, he received a Ph.D. in Mathematics in 1963 and then remained on the mathematics faculty. Throughout this period he continued to be involved with software development, serving as consultant to Burroughs Corporation from 1960-1968 and as editor of Programming Languages for ACM publications from 1964-1967.

He joined Stanford University as Professor of Computer Science in 1968, and was appointed to Stanford's first endowed chair in computer science nine years later. As a university professor he introduced a variety of new courses into the curriculum, notably Data Structures and Concrete Mathematics. In 1993 he became Professor Emeritus of The Art of Computer Programming. He has supervised the dissertations of 28 students.

Knuth began in 1962 to prepare textbooks about programming techniques, and this work evolved into a projected seven-volume series entitled The Art of Computer Programming. Volumes 1-3 first appeared in 1968, 1969, and 1973. Having revised these three in 1997, he is now working full time on the remaining volumes. Volume 4A appeared at the beginning of 2011. More than one million copies have already been printed, including translations into ten languages.

He took ten years off from that project to work on digital typography, developing the TeX system for document preparation and the METAFONT system for alphabet design. Noteworthy by-products of those activities were the WEB and CWEB languages for structured documentation, and the accompanying methodology of Literate Programming. TeX is now used to produce most of the world's scientific literature in physics and mathematics.

His research papers have been instrumental in establishing several subareas of computer science and software engineering: LR(k) parsing; attribute grammars; the Knuth-Bendix algorithm for axiomatic reasoning; empirical studies of user programs and profiles; analysis of algorithms. In general, his works have been directed towards the search for a proper balance between theory and practice.

Professor Knuth received the ACM Turing Award in 1974 and became a Fellow of the British Computer Society in 1980, an Honorary Member of the IEEE in 1982. He is a member of the American Academy of Arts and Sciences, the National Academy of Sciences, and the National Academy of Engineering; he is also a foreign associate of l'Academie des Sciences (Paris), Det Norske Videnskaps-Akademi (Oslo), Bayerische Akademie der Wissenschaften (Munich), the Royal Society (London), and Rossiiskaya Akademia Nauk (Moscow). He holds five patents and has published approximately 160 papers in addition to his 28 books. He received the Medal of Science from President Carter in 1979, the American Mathematical Society's Steele Prize for expository writing in 1986, the New York Academy of Sciences Award in 1987, the J.D. Warnier Prize for software methodology in 1989, the Adelskøld Medal from the Swedish Academy of Sciences in 1994, the Harvey Prize from the Technion in 1995, and the Kyoto Prize for advanced technology in 1996. He was a charter recipient of the IEEE Computer Pioneer Award in 1982, after having received the IEEE Computer Society's W. Wallace McDowell Award in 1980; he received the IEEE's John von Neumann Medal in 1995. He holds honorary doctorates from Oxford University, the University of Paris, St. Petersburg University, and more than a dozen colleges and universities in America.

Professor Knuth lives on the Stanford campus with his wife, Jill. They have two children, John and Jennifer. Music is his main avocation.

Customer Reviews

Most Helpful Customer Reviews

186 of 192 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)   

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

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.

41 of 41 people found the following review helpful:

5.0 out of 5 stars I wish every book were written like this!, December 13, 2005

By 

Anthony Widjaja To (Toronto, ON Canada) - See all my reviews
(REAL NAME)   

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

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

62 of 65 people found the following review helpful:

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

By 

N. Novik (New York, NY USA) - See all my reviews
(REAL NAME)   

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

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.