Concrete Mathematics Knuth

[Amilcar Labrosse]

ConcreteMathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, first published in 1989, is a textbook that is widely used in computer-science departments as a substantive but light-hearted treatment of the analysis of algorithms.

The book provides mathematical knowledge and skills for computer science, especially for the analysis of algorithms. According to the preface, the topics in Concrete Mathematics are "a blend of CONtinuous and disCRETE mathematics". Calculus is frequently used in the explanations and exercises. The term "concrete mathematics" also denotes a complement to "abstract mathematics".

The book is based on a course begun in 1970 by Knuth at Stanford University. The book expands on the material (approximately 100 pages)[1] in the "Mathematical Preliminaries"[2] section of Knuth's The Art of Computer Programming. Consequently, some readers use it as an introduction to that series of books.

Concrete Mathematics has an informal and often humorous style. The authors reject what they see as the dry style of most mathematics textbooks. The margins contain "mathematical graffiti", comments submitted by the text's first editors: Knuth and Patashnik's students at Stanford.

Introduction tothe mathematics that supports advanced computer programming and theanalysis of algorithms. An indispensable text and reference not only forcomputer scientists --- the authors themselves rely heavily upon it ---but for serious users of mathematics in virtually every discipline.Based on the course Concrete Mathematics taught by Knuth at StanfordUniversity from 1970--1989. The second edition includes importantnew material about the revolutionary Gosper-Zeilberger algorithm formechanical summation.Complete answers are provided for more than 500 exercises.

For a list of corrections to known errors in the pre-1998 printingsof the second edition,you may download the1994--1997 errata file in compressed PostScript format(74K bytes). This file was generated by the TeX fileerrata97.texin directoryftp.cs.stanford.edu:pub/concretemath.errata.oldusing special macros and fonts found in that directory. Errata listsfor various printings of the first edition can also be found there.See also the list oferrors corrected between January 1998 and May 2013,which is in HTML format.

DO NOT SEND EMAIL TO KNUTH-BUG EXCEPT TO REPORT ERRORS IN BOOKS!And if you do report an error via email, please do notinclude attachments of any kind; your message should bereadable on brand-X operating systems for all values of X.

SPECIAL NOTE TO THE SPEAKERS OF FRENCH AND OTHER EXOTIC LANGUAGES:Numerous quotations and bibliographic citations found in this book have beencopied verbatim from the original sources. If you believe you havefound a typographic error, you must prove it by showing that theoriginal was incorrectly transcribed; believe it or not, your languagehas changed over the years, just as English has.

Midterm and final exams from the last two times I taught this courseat Stanford (1988 and 1989) are now available, together with the answers,as compressed PostScript files. The teaching assistants who helped toprepare these exams were Sheralyn Listgarten and Sridhar Raman (1988);Alan Hu and Robert Kennedy (1989).

My own feeling on this is that if you are an undergraduate in an engineering discipline, with the usual math sequence behind you (e.g. calculus I,II,III, & linear algebra), you will have a difficult time with Concrete Mathematics.

Concrete Mathematics is an amazing book, but it assumes you already know the basics that would be taught in a 1-semester course on the subject. The problems are superbly gauged, and even the answers (which are provided for all the exercises) often require significant thought to understand. I am currently halfway through it and am just amazed at its density, how well written it is, and how perfectly the answers help one to solve the respective exercise without just giving the result away.

It would help to know what math classes you've covered thus far. Knowing some basics in calculus will certainly help. From one of your comments below your question, it seems as though you haven't had any calculus, it would be good to cover some of the material typically covered in a calculus survey course, or 1st semester calculus. Spivak's Calculus was one of the recommended texts; you could also learn calculus, or supplement your study of a text, with on-line video-lectures and tutoring: I highly recommend that you visit The Khan Academy website: everything offered on the site is free, and it has built a great deal of credibility (e.g. Bill Gates has offered to sponsor the site.) Not only does the site offer lessons and exercises in calculus; it also covers geometry, trigonometry, and algebra. It is very extensive and a good resource for "brushing up" on previous learning too.

Now, from my take of the preface to Concrete Mathematics (see link to the book's preface below), the book was, by design, written to make the content accessible to a "wider audience (including [college] sophomores)", and hence, doesn't seem to assume any intensive background in college math. So, I think you could probably "jump right into" the book; if you do encounter any difficulties along the way, the book has an extensive bibliography to which you can refer, or a quick web search (Google, Wikipedia, MathWorld, etc.) of the topic causing you problems will turn up lots of resources to help you out.

However, if you are really unsure of your capacity to master Concrete Mathematics at this point in time, then by all means, prepare using some of the suggestions cited here. Discrete math might provide some preparation prior to reading Concrete Mathematics, but it seems to me that the relevant content from discrete mathematics is covered in the text. It certainly wouldn't hurt to study discrete mathematics (perhaps take a look at Kenneth Rosen's Discrete Mathematics and its Applications); it all depends on the time-frame you have available, your level of commitment, your capacity to stay focused, and the confidence you have in your abilities.

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

Chapter 5 Binomial Coefficients 5.1 Basic Identities 5.2 Basic Practice 5.3 Tricks of the Trade 5.4 Generating Functions 5.5 Hypergeometric Functions 5.6 Hypergeometric Transformations 5.7 Partial Hypergeometric Sums 5.8 Mechanical Summation Exercises

Chapter 7 Generating Functions 7.1 Domino Theory and Change 7.2 Basic Maneuvers 7.3 Solving Recurrences 7.4 Special Generating Functions 7.5 Convolutions 7.6 Exponential Generating Functions 7.7 Dirichlet Generating Functions Exercises

It's never late to add an answer. Especially if it serves as reference to others. I'm a double major (senior) in CS and math. Compared to a common CS student my math knowledge is far superior, especially after taking courses in abstract algebra, real analysis, and so on that really changed my way of thinking, even more when it comes to write proofs. However, even with all these I must say that Concrete Mathematics is a tough reading. Sometimes I find myself looking at some answers in the back, because honestly it's hard material. Even though the authors, especially Knuth, are acclaimed experts, that does not mean they make the best teachers. People sometimes lie when they say it was not that hard just to seem smart. Do not believe them. The authors assume too much from the readers to be honest. You will struggle, but you will learn. If you don't know about a concept search the definition somewhere else, compare it to the one in the book if there's any. You will forget many things momentarily but in the long run they'll be there, and when the moment comes you will remember you saw it in a book, you will review it and you will apply it. That's all you need.

Sorry for being late to the party, but I have some recommendations that I feel are very helpful for prepping for Concrete Mathematics. I agree with all previously posted answers and think they are pretty on key. I haven't read Concrete Mathematics yet, but I am currently taking a discrete math course at Utah State. After taking Calc. I, and II and my current Discrete Math course I feel comfortable with all the notation I have seen so far in the book. Linear Algebra was not a pre-requisite for Discrete Math at my university, but at times I wish I had taken it. If this book is a reflection of my current class (which in seems in the most part to be) I would say you can most likely get by without Linear Algebra (by only learning as you are going), but I am considering taking a course in it online now since I wish I better understood the concepts.

Now onto my recommendations. I know you asked for books, but I personally feel you should try and take some math courses from MIT OpenCourseWare. Yeah it isn't books, but you can download and watch course lectures from the professors, and they have assigned books for the courses that you can buy yourself. They also have assigned homework that you can work through and other course materials.

I believe as well as amWhy that Khan Academy is a great resource for learning mathematics, but I really enjoy having the class room feel of taking an MIT OpenCourseWare course and personally prefer the MIT OCW over Khan Academy. I personally haven't finished the Mathematics for Computer Scientists course at MIT OCW, but I did start it to prep for my Discrete Math course at my university and it was a major help. I plan to finish Mathematics for Computer Scientists along with Concrete Mathematics, because I enjoyed taking the beggining of the OCW course so much.

3a8082e126