5 ms·

Ask HN: Math behind Algorithms

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?

tiberius 17y ago
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 17y ago
  The appendices at the end? Added it to my list. Thanks!
  - tiberius 17y ago
    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 17y ago
"Concrete Math" by Graham, Knuth, and Patashnik.
- rumpelstiltskin 17y ago
  The entire book?
  - ganley 17y ago
    Not necessarily, but the question wasn't specific enough to recommend a subset. It's all potentially relevant.
    - deleted 17y ago
      [deleted]
    - rumpelstiltskin 17y ago
      Cool. I'll look for the applicable sections within it. Thanks
  - eru 17y ago
    It's definitely worth browsing. Do as many exercises as you feel like.
- manvsmachine 17y ago
  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.
  - rumpelstiltskin 17y ago
    That's exactly what I was afraid of.
  - almost 17y ago
    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 17y ago
[deleted]
csomar 17y ago
at this case i prefer you follow a university lessons, may be it'll be better. (I just think so)
emacdona 17y ago
You should probably add Knuth's Volume 1 ( Fundamental Algorithms) to your list: http://www.amazon.com/Art-Computer-Programming-Fundamental-Algorithms/dp/0201896834/ref=sr_1_3?ie=UTF8&s=books&qid=1242733059&sr=1-3 http://www.amazon.com/Art-Computer-Programming-Fundamental-A... The first few sections cover some mathematical background.
pookleblinky 17y ago
http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one/ 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/ http://www.cs.sunysb.edu/~algorith/video-lectures/ is another great source for video lectures. http://en.wikipedia.org/wiki/List_of_algorithms 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/ 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-notation-do-you-use-it http://stackoverflow.com/questions/133008/what-is-big-o-nota...
adatta02 17y ago
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 17y ago
  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.
pkrumins 17y ago
I recommend Skiena's "The Algorithm Design Manual (2nd ed)": http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/freesciencand-20 http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...
amelim 17y ago
Try Algorithms by Dasgupta, Papadimitriou, and Vazirani. It's quite a short read and you can get it for free here: http://www.e-booksdirectory.com/details.php?ebook=1050 http://www.e-booksdirectory.com/details.php?ebook=1050
PaulMorgan 17y ago
Look for any book on Finite Mathematics.
mnemonicsloth 17y ago
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-Computer-Science/6-046JFall-2005/CourseHome/ 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.

tiberius 17y ago

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 17y ago
The appendices at the end? Added it to my list. Thanks!
- tiberius 17y ago
  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 17y ago

"Concrete Math" by Graham, Knuth, and Patashnik.

rumpelstiltskin 17y ago
The entire book?
- ganley 17y ago
  Not necessarily, but the question wasn't specific enough to recommend a subset. It's all potentially relevant.
  - deleted 17y ago
    [deleted]
  - rumpelstiltskin 17y ago
    Cool. I'll look for the applicable sections within it. Thanks
- eru 17y ago
  It's definitely worth browsing. Do as many exercises as you feel like.
manvsmachine 17y ago
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.
- rumpelstiltskin 17y ago
  That's exactly what I was afraid of.
- almost 17y ago
  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 17y ago

[deleted]

csomar 17y ago

at this case i prefer you follow a university lessons, may be it'll be better. (I just think so)

emacdona 17y ago

You should probably add Knuth's Volume 1 ( Fundamental Algorithms) to your list: http://www.amazon.com/Art-Computer-Programming-Fundamental-Algorithms/dp/0201896834/ref=sr_1_3?ie=UTF8&s=books&qid=1242733059&sr=1-3 http://www.amazon.com/Art-Computer-Programming-Fundamental-A... The first few sections cover some mathematical background.

pookleblinky 17y ago

http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-one/ 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/ http://www.cs.sunysb.edu/~algorith/video-lectures/ is another great source for video lectures. http://en.wikipedia.org/wiki/List_of_algorithms 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/ 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-notation-do-you-use-it http://stackoverflow.com/questions/133008/what-is-big-o-nota...

adatta02 17y ago

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 17y ago
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.

pkrumins 17y ago

I recommend Skiena's "The Algorithm Design Manual (2nd ed)": http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/dp/1848000693/freesciencand-20 http://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena/...

amelim 17y ago

Try Algorithms by Dasgupta, Papadimitriou, and Vazirani. It's quite a short read and you can get it for free here: http://www.e-booksdirectory.com/details.php?ebook=1050 http://www.e-booksdirectory.com/details.php?ebook=1050

PaulMorgan 17y ago

Look for any book on Finite Mathematics.

mnemonicsloth 17y ago

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-Computer-Science/6-046JFall-2005/CourseHome/ 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.