Programming Languages (both application and the concepts behind them)
As for what to learn, here is THE BEST link: http://matt.might.net/articles/what-cs-majors-should-know/. It covers all the topics I mentioned, and then some, and provides links to books/resources about everything. If you're serious about self studying Comp sci, that page has all the links and info you need to start.
To a certain extent I agree with Joel Spolsky's old article on Java schools. The one gripe I would have to make is that I believe that there are many useful tasks which are hard more than for the sake of being hard. My compiler's course was quite difficult but at the same time very informative. One thing we didn't do is write a parser. When I asked my professor (now advisor) why not, he responded that writing a parser is more of a character-building exercise. I tend to agree. While very tricky, I find that in the context of university classes so much time is spent writing a parser that more interesting topics in compilers are completely omitted. There's always benefit in deeper understanding, but one must try to identify the richest areas for learning.
It doesn't really matter what universities do or don't teach. If a subject is of interest you should learn it. I thought everything you and the linked article listed made sense.
"Introduction to Algorithms" a.k.a. "CLRS" http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...
I think this is all (and probably more than) you really "need" if you want to know CS for programming, and an enjoyable read too.
Last month (about 5 years after I took the course), I went through to review some stuff that I'd looked at more recently. Specifically, I had worked out Dijkstra's algorithm on my own and finally understood how the heck it actually worked. I then opened CLRS to check their proof. What I saw blew my mind in terms of sheer obfuscation. Despite having a very clear understanding in my head of the core concept behind the algorithm, I read their proof and was just amazed at how little it actually explained about the simple idea that ties the whole thing together. That by itself isn't a huge deal, because some proofs are just hard to follow. What really upset me was that there was practically no surrounding discussion of the intuition behind the algorithm. Behind all the rigor of mathematics lies very simple and powerful ideas. This book did nothing to emphasize those simple ideas. It's a real travesty to be honest :(
If you're looking for something more accessible, I've heard that The Algorithm Design Manual by Steve Skiena is better. Whatever you choose, though, please stay away from CLRS.
edit: I just found this review of CLRS on Amazon (http://www.amazon.com/review/R2FI8CA368KWGE/ref=cm_cr_pr_per...). It's the top comment for this book and sort of gets at the issue:
With that said, this book falls short in one MAJOR area, explanations. Too often explanations are left out and left as exercises and there are no solutions to the exercises! Or details are replaced by ambiguous statements such as of "cleary, this works", or "it is easy to see that this ...". I get the concept of learning by doing, really I do, but there should be some kind of solutions so the student can CHECK his/her understanding of the material and sometimes the exercises are not about advanced aspects of a concept, sometimes it is the core material. Even if the solution manual only contained a simple answer without the work. Not only would it help tremendously but the purpose of doing the exercises would be preserved; that is the student getting his/her "hands dirty" and working out a problem.
For the love everything good and pure in this universe, I really wish writers of mathematical books would stop using statements like "clearly this works" or "it is easy to see", "it is obvious" etc. While that may be true for you and your brilliant circle of colleagues, everything is not always clear and obvious to your readers. Save all of that ambiguity for your research paper.
A great book should deliver in two areas; it should challenge and it should inform. The challenge is there, no doubt. However in some ways it fails to inform the reader. The authors should really think about releasing a students solution manual to help students learn better. I take away two stars for the reasons stated about
CLRS is about algorithm analysis and formally proving that they behave in certain ways - like proving that quicksort has a guaranteed worst case of O(n^2) and an average case of O(n log n). Being able to work with proofs such as those is fairly fundamental to being a Computer Scientist in the strict, academic, sense. That being said, it should not be used as book to teach data structures or algorithms without formal proofs having been taught first - without the maths background the book is going to be very hard going.
The Algorithm Design Manual on the other hand, is more like a literature review for a collection of algorithms/families of algorithms (75, claims the copy infront of me). For each of them it gives an overview of the class of problems you'd apply the algorithm to, a run through of the algorithm (some with pseudo code) and discussion about the algorithm and times when the author has used it, and then pointers to more in depth sources. CRLS and Knuth are cited considerably, which should give you an idea about the relative stature of the two books being compared here.
Ultimately, they're both good books but for different audiences. The Algorithm Design Manual is by far the easier read, not least of which because it's not trying to be an academic text and is replete with anecdotes from the author. It's an excellent overview of the techniques available to the practicing developer - the ones who work in fields where you might need to whip up a quick Bin Packing routine anyway. CLRS is a lot harder to get through, but it will teach you how to prove that your algorithms will do what they should.
When it comes down to it, I'd say that CLRS is for the Computer Scientist while TADM is for the practitioner and I'm glad I own both.
http://ocw.mit.edu/courses/electrical-engineering-and-comput... - Very good course covering the most crucial theoretical things every programmer should now
http://aduni.org/courses/ - Good discrete mathematics, algorithms, theory of computation courses (I recommend "taking" them in this order) without assuming any prerequisites
http://ocw.mit.edu/courses/electrical-engineering-and-comput... - More sophisticated "CS 101" kind of course
I think almost everyone with some programming experience should be able to work through them in the sequence listed in one year perhaps, at a satisfying level of detail. At the same time, many people programming professionally lack mastery of this basic material.
Most exercises don't require an interpreter, which is nice if you need a break from screentime. But I do enjoy working through some of them in Racket or even Pixie Scheme. TLS isn't free or available in a digital format (AFAIK), but the book is inexpensive and very portable.
Also, I want to point out that "essential readings" is not the right attitude. In order to really make progress you're going to need to get your hands dirty and work though some examples. One very good exercise is to write an interpreter for a language you invent.
Then I would pick up Randall Hyde's books on "How to Write Great Code" series - he starts out with machine fundamentals (stuff you would typically learn in an Assembly or computer engineering course minus the Assembly).
Then I would learn some type of Assembly (again I recommend Randall Hyde).
Then, IMHO follow @BlackJack's comment of subject matter.
NOTE: I'm a self educated programmer.
You are going to find topics like:
* Regular Languages/Expressions
* Nonregular Languages
* Context Free Languages
* Turing Machines
* Decidable vs. Undecidable Problems
* Halting Problem
I written about some of these topics in an article last year that might give you a very small introduction to finite state machines:
Definitely yes, and yes. I suppose I want to see a few examples of writing better code, see how and why things break when they scale, understand useful principles that I just "worked around" before (ie recursive functions), and then also some primers on other subjects - so for example I studied poli sci, but they made me take anthropology, geography, economics and some other related but not completely aligned fields. What are some examples to complement web dev?
For programming specifically you can learn by doing more than reading. Just like Maths you have to have solved a problem or two. So hope the following inspires you and in the case of codeschool's rails for zombies or code academy - it means you can learn by doing.
Kicks ass. Unless you are scared of zombies.
YC Startup if I remember correctly. Beautiful.
Computer Science, Turing Turing Turing:
For some serious inspiration the first ever essay we wrote at Manchester in Year 1 of CS was The Life and Times of Alan Turing. His huge impact still hadn't hit me then. The story of Alan Turing is told in so many different ways that to learn about him is to learn about the type of mind that led us to where we are now. His impact at Bletchley Park breaking the German Enigma code, then at Manchester his work not only seeded AI as we know it but showed how Mathematics could help us understand the code behind nature. These deep roots of CS are what keep you going through the more incomprehensible CS books and difficult challenges.
I just found this:
Breaking the Code: Biography of Alan Turing (Derek Jacobi, BBC, 1996)
Looks like I am staying up working a little longer! If only BBC Programs could be streamed on demand I would pay for one daily. There were numerous programs on Turing including an episode from the series The Code - Numbers which was the type of programme that should always be available to the world and makes you wonder why the BBC doesn't unleash it's potential... Another story...
I really value all the helpful comments here - thank you for your practical advice guys ;-)
I'm an industry programmer and pursued a lot of Comp Sci self-study in order to become a "better programmer", an "effective programmer", and most importantly "better able to reason about my programs".
Being versed in both is important so the reading list, IMHO, should be mixed!