This book <<The Nature of Computation>>[0] has the best explanation I have ever seen.

[0]: https://www.amazon.com/Nature-Computation-Cristopher-Moore-d...

There is large body of work from the mid 1980s and early 1990s that addresses the question of hardness, sensitivity and robustness from various statistical physics/computer science collaborations. Of course, it is still ongoing, but that was a big period. The basic thrust of this program is to take methods from statistical mechanics and use them calculate not just worst case complexity, but also average case, best case, and everything in between. It is hard to think of a reference to end all references, but as far as books go you might want to check out: http://www.amazon.com/The-Nature-Computation-Cristopher-Moor.... For an article that briefly addresses some results related to kSAT there is: http://www.cs.cornell.edu/selman/papers/pdf/99.nature.phase.....

What do you want to learn? Programming or CS? CS is more than just programming, and CS theory is more than just Algorithms & Data Structures.

If you want to learn about Algorithms and Data Structures and you have a strong math background, then CLRS is the book to get: http://www.amazon.com/Introduction-Algorithms-Thomas-H-Corme...

An undergraduate CS curriculum will mostly cover the parts I-VI of the book (that's around 768 pages) plus a few chapters from the "Selected Topics Chapter" (we covered Linear Programming and String Matching). Mind you, this book is very theoretical, and all algorithms are given in pseudocode, so if you don't know any programming language, you might have to go with a an algorithms textbook that is more practical. In my DS course we had to implement a Red-Black tree and a binomial heap in Java, and in my Algorithms course we only wrote pseudocode.

Maybe Sedgewick's (Knuth was his PhD advisor!) "Algorithms (4th ed)" will be a better choice for a beginner, as it shows you algorithm implementations in Java: http://www.amazon.com/Algorithms-4th-Edition-Robert-Sedgewic... (If you decide to go this route, you might as well take his two Algorithms courses on Coursera, they will really help).

There are also a bunch of Python-based introductions to computer science which have a broader focus than just teaching specific data structures and algorithms. Some of them emphasize proper program design, debugging and problem solving. I haven't read any of them, so I can't vouch for them, but here are a few of the more popular ones:

* http://www.amazon.com/Introduction-Computation-Programming-U...

This book was written to go along with John's edX course: https://www.edx.org/course/mitx/mitx-6-00-1x-introduction-co...

* http://www.amazon.com/Python-Programming-Introduction-Comput...

Oh and btw, there's also the Theory of Computation, which is a major part of CS theory. Here are a few MOOCs and recommended books on the subject:

MOOCS:

* https://www.coursera.org/course/automata

* https://www.udacity.com/course/cs313

Books:

* http://www.amazon.com/Introduction-Theory-Computation-Michae...

Sipser's book is probably the best introduction to the theory of computation, and I believe its last chapter deals with Complexity theory as well.

* http://www.amazon.com/The-Nature-Computation-Cristopher-Moor...

I loved this book very much. It has a very informal and conversational style (don't let it fool you, the problem sets can be HARD).

* http://www.amazon.com/Computational-Complexity-A-Modern-Appr...

Once you are familiar with some computation models, its time to study computational complexity and this is one of the best books on the subjects. It is used both for graduate and undergraduate courses.