Recommendations for discrete math resources

Question

Hi,

I recently Graduated from uni in the UK but I only scraped through the Algorithmic and Mathsy units that I was made to do and am now finding that I'd actually like to know how to do some of the stuff that was taught.

In particular I'm trying to follow the MIT lectures of the Algorithms lectures on Google Video. I'm finding it very hard to follow the proofs for things such as Big O notation and recurrences.

I was wondering if anyone could recommend some good resources for me to look at to get to know this type of math and become more familiar with it.

Thanks

Answer 1

I have heard this book is good.

The Elsevier site also has a lot of articles and white papers.

Answer 2

Big-O is explained in many questions, e.g. here and here. Any book on algorithms will cover it, too. A good book on algorithms is "Introduction to Algorithms". A book on discrete maths is most likely overkill if you are just interested in algorithms.

Answer 3

For algorithms and asymptotic analysis (big O stuff), the best book I've ever read is the CLRS Introduction to Algorithms book. It's an amazing resource.

Answer 4

I recommend Concrete Mathematics (A Foundation for Computer Science) by Graham, Knuth, and Patashnik. The margin notes in the book are quite funny (and corny at times), and the main text is not bad too <rimshot />

Answer 5

Mathematics for Computer Science is a prerequisite for the MIT Introduction to Algorithms class, and asymptotic notation is covered in the second half of Lecture 11 [pdf].

It's covered again in Lecture 2 [pdf] of Introduction to Algorithms (in case you haven't found the notes).