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

This book is classic Knuth: brilliant, comprehensive, inviting, and playful. Highly, highly recommended. This book is ideal for self-study.Material covered includes the basics of discrete math, plus some extras needed for analysis of algorithms. There is an explicit and polemical slant towards a concrete (Knuth calls it 'Eulerian') approach, but this basically just means the emphasis is on explicit calculation and motivating examples, rather than 'elegant' formality and abstraction.In terms of topics, the book starts with a chapter introducing recurrences, then guides the reader through developing familiarity and calculational skill with sums and sigma notation; floors and ceilings; modular arithmetic and a bit of number theory; binomial coefficients and special functions, finally culminating with generating functions, which provide a general framework for solving recurrences encountered in earlier chapters. There are also a couple of chapters on discrete probability and asymptotics, which round out the stated goal of the book: covering preparatory mathematical material needed for the analysis of algorithms in Knuth's Art of Computer Programming.As with TAOCP, the problem sets are as enjoyable and carefully constructed as the exposition, and the solutions are included in the back of the book (about 500 pages of exposition, and about 100 pages of solutions). These problems could easily keep an interested person busy for a lifetime. They are each graded using Knuth's customary scale, and range from the trivially easy to open research problems.

There are so many font and ligature issues in the kindle version of this book, it is virtually unuseable. But the print version is great. Other reviewers take issue with the lack of examples for some of the more advanced topics, and one reviewer attributes other's favorable reviews to Knuth "fan-boy-ism". I feel Knuth is (deservedly) a legend because of the topics he chooses and the detail in which he covers them--not because he always has the best way of presenting the information to students. Even though his books include exercises, I don't consider any of Knuth's books to be good textbooks and I am glad I never had to take a course where any of his books were used as the main text. I have been writing scientific applications software for over forty years, and Knuth's books have proven to be extremely valuable reference books for me. Compare the topics covered in Knuth's books to other algorithm books like Sedgwick or Cormen, et al. and you will find lots of useful information that is unique to Knuth.

Amazon did a great logistics job. I really like what this book brings to the table. A rigorous and yet pleasant presentation of maths for computer scientists.

I love this book.It's extremely dense, which is great for me because I will keep learning from it for months or years to come.If you're relatively new to the subject, like me, a lot of this book won't be easy to comprehend the first time around, however with determination and online resources for help, you can get through it.Even without online resources, if you keep going when you don't understand something, and try to work out the examples on paper, you will get far.After studying this book for a while, go back to the sections that you missed the first time and they should make more sense.Try as many of the exercises as you can, some are very difficult, but others can be accomplished the first time around.This book is not for the faint of heart. If you aren't using it for a class, it will take a lot of dedication to make it through. That said, it's one of the best resources for learning discrete and continuous mathematics that relate to computer science.A great precursor to many of the great algorithm books.

I originally bought this book as a source of remedial study following the end of my US state school CS undergrad experience (I completed a BS Computer Science in 2013, > 3.5 GPA), and as preparation for V1 & V4 of TAOCP. I use the word remedial here in the sense that I felt that I was missing a critical foundation in the mathematical analysis and derivation of algorithms, even after the course-work of that degree. I've done 3 chapters of it in full, and I will mention a number of things that other reviews haven't talked about. Due to the horrendous time commitment of this book, I strongly suspect this is because those reviewers haven't actually worked through it, and have instead chosen to skim and allow Knuth fanboyism, along with the desire for mutual association, to cloud their opinions. I'm revoking a star simply to balance those reviews out, and so that graduates in similar situations have an actual informed critical opinion of this book to find among the reviews.Take-Aways (As of Ch 3):There are many aspects of summations, integer functions, and proofing that: I never saw covered in my CS degree, are unforgettable, and can be immediately applied to most algorithm research. Those alone make this book worth every penny. Further, the problems posed by this book are more than just repeated mechanics, as I have seen in books like those mentioned below. Each problem is carefully chosen, thorough, and exposes multiple aspects of each topic. They really do weed out many faults that I wasn't really exposed to- as a small example: the importance of ensuring validity of n-1 and n-2 hypothesis & base cases during an induction proof.The Bad:Students educated through a contemporary CS track at most American uni's, I believe, (e.g. Rosen Discrete Math, Cormen Algorithms) will find this book both terrifyingly terse and frustratingly paced. In many cases, examples are given without derivation. In many cases, important points are made without obvious connection to previous topics. This is not without a solution however, and getting through this book is often an acquired technique of paper noting things as-you-go, as well as a learned hyper-literacy. The terseness is also a double-edged sword, as sometimes I found it useful as an extra opportunity to practice the taught methods to see if I could come to the same result. Further, the reader should be prepared to go back and review propositional logic & university calculus theorems (atleast FTC, definite vs indefinite integrals). For example, the description of sum by parts in the section on finite calculus assumes _much_ from the reader, and being able to use university calc. as a point of reference to get through that is helpful.A lot of exercises are tersely explained in both problem and solution. Further, many solutions are totally left-field (having little to do with material in the book). This isn't necessarily bad, as even taking the wrong path to a solution is very educational. However, at some point the reader has to make a judgment as to how long to commit to a certain problem. Many terse problems & left-field solutions instill the wrong judgment: quitting too early.Conclusion:Attention to detail & extra work is necessary to overcome the terseness of this particular beast, but it's worth it. I recommend this book for developers confronted with algorithm optimization problems, as a well as for a different take on parts of discrete math, and definitely for students coming out of a US state school CS program, the last which this book complements very well. Having worked through some of V1 TAOCP, I would also say that the book is effective in expanding upon its math underpinnings (V1 at-least), and incidentally, does give one confidence to tackle Knuth's other works.