HN Explorer

Ask HN: Math behind Algorithms

21 points by rumpelstiltskin ↗ HN
I'm planning to spend the next few weeks beefing up on algorithms - starting with Algorithms in a Nutshell, followed by Algorithm Design Manual and Algorithms by Dasgupta.

Before I start these books, I wanted a primer on the math behind algorithms. A friend suggested I look at Velleman's "How to Prove It". Anyone have any other recommendations?

22 comments

[ 2.7 ms ] story [ 60.1 ms ] thread
tiberius
The math section of Cormen, Leiserson, Rivest "An Introduction to Algorithms" is a good introductory math text for CS people (the remainder of the book is also excellent).
rumpelstiltskin
The appendices at the end? Added it to my list. Thanks!
tiberius
I was thinking of the first few chapters (Part I of the book). But your question was rather generic, actually there are mathematical techniques sprinkled through the whole book.
ganley
"Concrete Math" by Graham, Knuth, and Patashnik.
rumpelstiltskin
The entire book?
ganley
Not necessarily, but the question wasn't specific enough to recommend a subset. It's all potentially relevant.
[deleted]
(comment deleted)
rumpelstiltskin
Cool. I'll look for the applicable sections within it. Thanks
eru
It's definitely worth browsing. Do as many exercises as you feel like.
manvsmachine
Beware, Concrete Math, from what I've heard, is great but very hardcore (but in a subtle, sneaky way). The reader is expected to have a very solid grasp of many areas of math before reading it, such as being an upper level math undergrad student. If this doesn't describe you, I'd also suggest starting with CLRS first.
almost
But it's written so well that it's a pleasure to repeatedly bang ones head against :) So go for it but expect to have to take it slowly... oh, and do the exercises otherwise it won't make sense.
[deleted]
(comment deleted)
csomar
at this case i prefer you follow a university lessons, may be it'll be better. (I just think so)
pookleblinky
http://www.catonmat.net/blog/mit-introduction-to-algorithms-... is a very good site, with videos of MIT lectures.

http://www.cs.sunysb.edu/~algorith/video-lectures/ is another great source for video lectures.

http://en.wikipedia.org/wiki/List_of_algorithms has a veritable zoo of algorithms. Best part: contribute to the pages and you'll learn it better than just reading. For a true zoo of algorithms to start off a search, http://www.itl.nist.gov/div897/sqg/dads/ is perhaps the best.

Stack Overflow's got many good threads on Big O and comparative complexities, for instance http://stackoverflow.com/questions/133008/what-is-big-o-nota...

adatta02
get yourself a discrete math textbook (I can't remember what I used). A sprinkling of things that will come up: set theory, probability (Bayesian), Big-O notation and associated meanings, worst/best/avg case analysis, amortized cost, induction, some algebra, ect

if you don't really understand all the math surrounding some fancy algorithm it probably isn't all that important. and everyone's favorite line in a CS proof is of course "without loss of generality".

likpok
A book i used and liked: Mathematical Thinking, by West and D'Angelo.

It's more than a discrete text (it covers construction of the reals, limits, etc), but it covered a lot.

PaulMorgan
Look for any book on Finite Mathematics.
mnemonicsloth
Intro to Algorithms by CLR is the best first book on the subject I know of. MIT has a complete set of lecture videos:

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Compute...

But based on my own (admittedly weird) experience, Algorithms per se might not be the best place to start. You might do better starting off with graph theory instead because:

1. It's an equally fundamental entree to the same theoretical CS material. Graphs abstract data structures like algorithms abstract programs.

1a. You wind up learning a lot of the same material.

2. The "core" of Algorithmic analysis is solving counting problems with recurrence relations, sort of like the way "canceling terms" is the core of high school algebra. It's easy to explain the concept in a few words, so it's easy to think you understand it, but you have to practice it in a lot of different contexts to really master the skill. There's also a lot of deep theory hiding below the surface. Graph theory, on the other hand, starts out with definitions that you can blow through in a day, and then builds progressively more complicated structures for you to analyze.

3. Most of the proofs in graph theory actually involve writing programs to construct an existence proof or verify a property. Obviously this is also true of algorithms, but the correspondence between proofs and programs is harder to see there.

4. Graph theory touches higher math in more accessible places than algorithmic analysis. You can analyze graphs with matrices, mess around with their eigenvalues (although I think the preferred term is "spectrum"), do some group theory -- "advanced undergraduate" stuff. The only place in higher math where algorithms really come into play is number theory, which requires a lot of theoretical machinery to make its sausages.