I don't know, Alice answered. Then, said the cat, it doesn't matter."
A good (non generic) answer to "What should I learn?" (asked by a self educated programmer here) depends on the answer to the question "What (kind of programmer) do you want to be?"
Step 1, answer the Cheshire cat! )
If this is a coincidence and you done it by mistake (i.e. mistakenly have not put a ':') then this is one sweet coincidence. If not, then kudos to you :)
(For the perplexed) In "Alice In Wonderland" the Cheshire Cat fades away till nothing is left but its grin So I removed the ":-" from ":-)".
I then looked at my primary programming language (C++) differently. I wasn't just always using vectors any longer. I knew when to use them and when to use a queue or stack or hash.
In short, studying algorithms and data structures and then applying what I studied in C++ made me a better programmer.
One in particular comes to mind, I was working a temp job during my 3rd year at college with a very talented friend who was self-taught. He had written a rather brilliant dynamic reporting system for a very large e-commerce site in Perl, allowing the management to interactively drill down into recent sales and inventory activity. It worked fine for a few years until the volume of data became very large. Try as he might he couldn't get the software to be performant any longer and had to resort to a 10-11 hour batch crunch every night with the output dumped out to static HTML files for the mgmt to review. Finally one night, the process failed -- out of memory. Throwing more hardware at it only bought another few days.
A dive into his code (most of which was really quite well done) turned up the following: he was using Perl hashes everywhere to operate on the data because they made the code easy to read and convenient to write and maintain. I rewrote many of the particularly inefficient parts to use arrays over a few weeks and suddenly, the entire batch took 10 minutes to run! A few more tweaks and we turned it off of batch mode and back into full interactive mode. Mgmt never had to wait more than a minute or two to return back a report of a huge amount of data.
The key of course was that he simply didn't understand how much overhead the associative arrays created because he didn't understand the data-structures involved. He had simply relied on the magic of the language to do that work for him. A few days spent with http://blob.perl.org/tpc/1998/Perl_Language_and_Modules/Perl... and he never made that mistake again.
CiteSeer (http://citeseerx.ist.psu.edu/) is an excellent place to find theses, research papers, etc., and it has local PDF / PS caches for many of them. Google Scholar (http://scholar.google.com/) also works, though many results will be behind academic paywalls (e.g. the ACM) - the "all X versions" link will often have alternative links, such as faculty pages, including PDFs / PSs.
I've read parts of volumes 1 and 3. This book is awesome if you have the time to digest it, but you get faster results from other books that are easier to read, like Cormen's Algorithms.
If you are expecting TAOCP to be an Algorithms textbook, you're going to be severely disappointed.
Personally, I find TAOCP to be highly underrated. I find Knuth to be an utter joy (and just yesterday, greatly enjoyed watching the video of the 16th Annual Christmas Tree lecture.)
CLRS is a great Algorithm textbook, but it's not the place to go to find why there is a Pi in the formula for the approximation of Catalan numbers.
But I'd be interested in knowing what books you refer to as far as giving faster results beyond that(TAOCP is dense which I'll agree makes it a difficult read). I've never found a book that covers the same information as TAOCP and while I hated every second of reading it when I was being forced to do so I have to admit the knowledge has served me well
Personally, I still think K&R is the best CS/programming book I've ever read.
(TAOCP is wonderful but I think the great majority of potential readers would be better served by Cormen/Leiserson/Rivest[/Stein]. But when you really need Knuth, nothing else will do.)
"Elaboration of these ideas [2-3 trees, and a way of representing them as binary trees -- gjm] has led to many additional flavors of balanced trees, most notably the red-black trees, also called symmetric binary B-trees or half-balanced trees" ... followed by a list of references to places where these other sorts of tree, including red-black trees, are discussed.
So, indeed, you wouldn't turn to Knuth for "red-black tree magic".
What it does do is give you depth of knowledge. It helps you to understand the part of the computer you've never even thought of if Java is the first language you ever learned.
However, because I know I will always do web programming I have definitely not focused on issues like compiler design, low level memory management , etc because most of the languages I use are either interpreted or compiled to bytecode and thus those areas are irrelevant
I would therefore argue it very much depends on what kind of work you wish to do - sure read some more in depth stuff but if you are doing web programming spending some of that time on product development knowledge, server administration, etc might be more beneficial.
 clearly some memory management is important in languages like Java and Objective C but using the built-in alloc/dealloc functionality is not really "low level understanding"
That seems like a pretty unwise assumption to me. In a decade or two the web may have changed beyond all recognition.
Programming may be completely different in a decade's time but I won't be programming. My era is now and that was always the plan to concentrate on web.
I fully respect the "career programmer" may need to choose differently but for many of us working as an engineer/programmer is simply a step in the journey. To go back to the OP, that's probably why I didn't feel inclined to study CS at university.
Lets say the next big thing in programming is GPU programming to compute massive volumes of data - I will still always do web programming.
Lets say I continue to move into strategy, product development etc - I will still always do web programming.
I just don't sit into one of the boxes perhaps you are trying to pigeon hole me into, maybe?
+Code Complete - A no nonsense approach to Software Engineering and other tasks related to development. The SE texts used in most college courses are far too advanced and abstract for undergrad students that have never worked on very large projects. This one delivers excellent advice for single programmers up through medium size groups.
+Some algorithm and data structure book - there are a lot of bad ones. Use Amazon ratings to try and find a good one. Work through the design of as many algorithms as possible, no matter how mundane or the fact that most practical languages have libraries that deliver this functionality. Know what algorithmic complexity is and memorize the complexities of often used data structures to help quickly choose while coding.
+An operating system design book (e.g. Operating System Concepts or Modern Operating Systems) - know how the OS packages RAM, storage, CPU scheduling, network, concurrency for userland programming.
After that, I recommend SICP.
When you are self-taught you easily end up with big holes in your knowledge, because you typically focus on what you need to know in your current project. These two books are great because they cover a lot of ground (different abstraction levels, different paradigms) while still remaining practical.
Even better, PG has now made On Lisp available for free: http://www.paulgraham.com/onlisp.html.
(I hate it when people say they learned nothing from schooling, computer science theory is dripping with practical usefulness. Unless you're just so damned brilliant you came up with compiler theory and basic AI and type theory and all kinds of other stuff all on your own. Which I don't believe.)
Back when he was still doing podcasts Joel Spolsky answered the similar question, which was partly "Does a good programmer without a CS degree really have a chance to get a job at Fogcreek?" (It's near the end of the page.)
He says that for a good self-taught programmer who began with a high-level language, say PHP or Java, who comes at programming from a practical perspective, there are a few important parts of the CS curriculum the person may have missed out on, and goes on to list some books that would help fill in those gaps.
Off the top of his head he named these books in about this order:
- Structure and Interpretation of Computer Programs (also free online)
- C Programming Language
- The Unix Programming Environment
- Introduction to Algorithms
He said that those books covered the aspects of the CS curriculum his company needs in a good programmer, e.g. being able to create algorithms for an uncommon data structure.
Those books all have the added advantage of having exercises, and all being a very pleasant read. SICP is an introduction to many of the big ideas in CS: data structures, streams, recursion, interpretation, compilation, register machines, etc., and their implementation in Scheme (a kind of Lisp). It's a great place to start. The next two focus on implementation details like pointers and memory allocation. They are compact, powerful books. The last, Introduction to Algorithms, seems misleadingly titled, as it is fairly comprehensive and used in both undergraduate and graduate courses. If you work your way through the entire book, chapeau!
Strong communication skills are powerful.