Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What book(s) do you recommend before Concrete Mathematics?

Is something like "Introduction to discrete Mathematics" enough?

share|improve this question
7  
What is your background? What makes you think that you are unable to tackle 'Concrete Mathematics' currently? Was there anything in particular in the book that seemed mysterious? –  Aaron Jun 4 '11 at 9:47
    
Mr. Knuth said it on the beginning, so if author expresses it himself, majority spreads rumor :) My background is that I'm CS student in software engineering very interested in compilers, low level programming and skill improvement, so here it is where TAOCP and other stuff takes place. –  pragmacoder Jun 4 '11 at 10:14
    
I think you will need to know some basic calculus (Spivak's book is my favorite, but I'm not sure it's good for beginners...) –  Gadi A Jun 4 '11 at 11:56
1  
I read the book in Class 11 or 12 (i.e., before college). Of course there were some parts of it I didn't understand at the time, and I just skipped them, but on the whole it's pretty self-contained. Just make sure you do as many exercises as you can. –  ShreevatsaR Jun 4 '11 at 18:04
1  
TAOCP first or prep for it with CM before? –  pragmacoder Jun 4 '11 at 18:48
show 3 more comments

2 Answers 2

up vote 12 down vote accepted

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.


For those who aren't familiar with the book Concrete Mathematics, an overview of the text can be found here. To save you some "web surfing time", I'll quote from that webpage below:

Subject Area: CS Basics (Logics, Discrete Mathematics) in CIDEC Library.

CONCRETE MATHEMATICS: A Foundation for Computer Science, 2nd ed
Authors:
* Ronald L. GRAHAM, 1935- , AT & T Bell Laboratories
* Donald Ervin KNUTH, 1938- , Stanford University
* Oren PATASHNIK, 1954- , Center for Communications Research
Publisher : Addison-Wesley Publishing Co. - Reading, Mass.
Bibliographic : Hardcover, ISBN: 0-201-55802-5 © 1994

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

CONTENTS

PREFACE (See Preface here)

Chapter 1 Recurrent Problems 1.1 The Tower of Hanoi 1.2 Lines in the Plane 1.3 The Josephus Problem Exercises

Chapter 2 Sums 2.1 Notation 2.2 Sums and Recurrences 2.3 Manipulation of Sums 2.4 Multiple Sums 2.5 General Methods 2.6 Finite and Infinite Calculus 2.7 Infinite Sums Exercises

Chapter 3 Integer Functions 3.1 Floors and Ceilings 3.2 Floor/Ceiling Applications 3.3 Floor/Ceiling Recurrences 3.4 'mod': The Binary Operation 3.5 Floor/Ceiling Sums Exercises

Chapter 4 Number Theory 4.1 Divisibility 4.4 Factorial Factors 4.5 Relative Primality 4.6 'mod': The Congruence Relation 4.7 Independent Residues 4.8 Additional Applications 4.9 Phi and Mu Exercises

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 6 Special Numbers 6.1 Stirling Numbers 6.2 Eulerian Numbers 6.3 Harmonic Numbers 6.4 Harmonic Summation 6.5 Bernoulli Numbers 6.6 Fibonacci Numbers 6.7 Continuants 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

Chapter 8 Discrete Probability 8.1 Definitions 8.2 Mean and Variance 8.3 Probability Generating Functions 8.4 Flipping Coins 8.5 Hashing Exercises

Chapter 9 Asymptotics 9.1 A Hierarchy 9.2 O Notation 9.3 O Manipulation 9.4 Two Asymptotic Tricks 9.5 Euler's Summation Formula 9.6 Final Summations Exercises

share|improve this answer
    
Well my math sub-courses covered in short period(not in positive meaning) functions, basics of trigonometry, geometry, linear algebra ... I mean it doesn't matter since I'll refresh my knowledge on the topic anyways. So basically you say I could start with it, but what about challenges, maybe it's better to take some ground beneath since I don't have time e.g. to think about on one solution 1 week so that's why I asked which books could accelerate my progress in CM and later in TAOCP. Thx –  pragmacoder Jun 4 '11 at 18:42
1  
Yes, I'd suggest that you take a survey course in Calculus, (or browse through Spivak's Calculus, e.g., work through problems - it could also serve as a reference to refer to later.) But perhaps more importantly, if you study Discrete math, you will, essentially, be introduced to some of the fundamentals pursued in greater detail in Concrete Math. I personally like Kenneth H. Rosen's *Discrete Mathematics and its Applications." I believe there's a solution manual for it, as well, which will help if you plan to study Discrete Math on your own. –  amWhy Jun 4 '11 at 18:51
    
Thank you for your help. –  pragmacoder Jun 6 '11 at 11:57
    
One more thing, Rosen's book is not suggested by the amazon ratings, what do you think about it? –  pragmacoder Jun 6 '11 at 12:06
    
One comment I have on Rosen's books: I've used them before as a student and as a professor, but I've not always been happy with them. Although the coverage is good, and the exposition is often excellent, they are often sloppily edited and contain an embarrassing number of errors. –  Fixee May 25 '12 at 19:01
show 6 more comments

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.

You would be much better served starting with an introductory text (I think Epp's Discrete Mathematics with Applications is excellent), and afterwards going to that book.

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.

But I have already been exposed to the discrete math basics and still find Concrete Mathematics is hard work.

The preface may imply it can be read by a wide audience - there may be college sophomores in engineering programs who can handle this material. But they would be the rare exception.

share|improve this answer
3  
I know Stanford students who used this book with Knuth as the prof, and they said the course was very painful. And these are presumably among the best undergrad CS majors in the world. –  Fixee May 25 '12 at 19:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.