[gcv]

I'm impressed that you chose to approach learning from a theoretical point of view. It will serve you well; you will understand algorithmic approaches which stump a lot of people who lack a theoretical background. (Please, no "I never got a CS degree, but I know what I'm doing" replies --- the HN audience is more competent than the average in the working world. I'm sick and tired of working with people with trade-school degrees in programming or "computer engineering" who do not understand binary search.)

To start, you should read SICP (http://mitpress.mit.edu/sicp/) and watch the lectures (http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussma...). You should probably do this before diving deeper into discrete math, algorithms, or theory of computation. SICP is almost completely unique in that it touches on all these topics, and puts them in the context of actual programming. It also happens to include solving fun problems along the way.

After that, you'll be well-prepared to have a ball in all aspects of CS. You can get more into pure hacking by learning languages (after Scheme, I recommend C, Python, Common Lisp, Haskell, and Prolog before jumping into more unexplored directions like Scala and Clojure), and following up by studying compilers and operating systems. You can get into a more job-oriented path by learning Java and C#. You can get into more algorithms by reading Cormen et al. and, of course, Knuth. You can get into pure theory by reading Sipser (wonderful, wonderful book).

[gaius]

I'd add The Little Schemer to the list of books.

[mechanical_fish]

A question: Cormen, then Knuth? Or the other way around? Or does it not matter?

[gcv]

I must sheepishly admit that I have not fully read Knuth. I've skimmed parts of Vol. 1-3 and looked up specific things, but I have not gone through every proof with a fine-tooth comb. (Far from it.) The book is enormously deep, very valuable if you follow all the math, insightful. At the same time, it doesn't cover a whole lot of topics, and with good reason: it isn't complete yet. Volume 4 has been in production for decades now, and being released piecemeal. CLRS (Cormen et al.) has less depth, but more breadth. The book covers introductory graph algorithms in reasonable detail, for example.

As a side note, Knuth presents examples using a synthetic machine language. Don't get me wrong: this is actually extremely cool, but you end up jumping between thinking about registers and then thinking about very high-level math. This shouldn't throw you off very much, but it makes me think that it shouldn't be the first or only algorithms text. CLRS, on the other hand, uses pretty dense pseudocode, lots of mutable state, and bad variable names. The longer algorithms can be hard to follow. I know that a 3rd edition will come out in a couple of years, maybe it'll fix that. Not sure.

Speaking for myself, I'm not sure I could plough through either Knuth or CLRS, from first to last page. I read books like that by reading introductions and then skipping around. By the time you get that far, you'll know what interests you and where you need to pick up knowledge. Certainly once you have dynamic programming techniques under your belt, you'll know enough to guide your own explorations.