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?
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...
The first few sections cover some mathematical background.
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.
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".
It's more than a discrete text (it covers construction of the reals, limits, etc), but it covered a lot.