Ask HN: What book to read to get a footing in CS theory?

Avoid books with a programming language in the title, because those will try to teach both basic programming and the interesting material.

https://smile.amazon.com/Algorithm-Design-Manual-Steven-Skie...

https://www.amazon.com/Algorithm-Design-Manual-Steven-Skiena...

Far more readable than the usual text (Cormen), the first half is a guide on how to select and design algorithms for the problems you encounter, and the second half is a whistle-stop tour of hundreds of well-known algorithms. The tour helped me a lot with X->Y esque issues where I was building bad solutions because I didn't know anything better could exist.

Incidentally, there's a lot more to CS theory than algorithms and data structures, but if you're asking on HN for a generic CS theory book, I reckon it's most likely an algorithms and data structures book that you're after.

O'Halloran/Bryant CSPP https://csapp.cs.cmu.edu/

David Money Harris Digital Design... https://booksite.elsevier.com/9780128000564/

Then there is also excellent BaseCS Podcast [2]

[1] https://bigmachine.io/products/the-imposters-handbook [2] https://www.codenewbie.org/basecs

Unless your friend is a natural born comp. scientist, she'll need someone to point out what's important, what's not, which exercises she must solve before moving on and which topics she can take in parallel if she needs a break.

Of course, a course takes time. But if someone doesn't find the time to take an online course, where will they find the time to (properly) read the book?

http://nature-of-computation.org/

- The Computational Beauty Of Nature, by William Gary Flake

- The Impostor’s Handbook, by Rob Conery

- The Elements Of Computing Systems, by Noam Nisan & Shimon Schocken

For computer architecture, Petzold's "Code" is wonderful.

All of the code you write is run by one or more CPUs; operating systems provide supporting software, they don't "run" programs (although they may schedule them for execution, which isn't the same).

</pedant-mode>

Broadly speaking there are two types of "CS Theory":

1. "What is computation and what can be computed?" That's what Wigderson's book is about. Complexity theory.

2. "What's the best way to compute something?" covered by "Introduction to Algorithms" and the like -- sth people ask on interview questions. In addition to the references here, http://people.cs.uchicago.edu/~laci/17discrete/ gives some good puzzles to work through.

Of course, a course takes time. But if someone doesn't find the time to take an online course, where will they find the time to (properly) read the book?

Computer science is much broader than that; it includes databases, AI (not the same as algorithms!), computer architecture, topics such as hardware interfacing, history of computing, and some overlap with areas in philosophy.

I didn't ever formally study CS, but I did read several books on algorithms. Especially notable is the seven-volume work "The Art of Computer Programming" by Donald Knuth; in particular the volumes "Fundamental Algorithms", "Sorting and Searching", and "Seminumerical Algorithms" are timeless masterpieces, entertaining and witty, and they totally nail their subject-matter. If you think CS is equivalent to "algorithms", then read these books.

N.B. I understand that some of these books have been re-written to use a revised version of Knuth's MIX machine language, to allow the examples to embody modern developments such as pipelines, caches, and parallelism. I haven't read these updated editions; no doubt they are even better than the originals.

But I think CS is a much broader field than algorithms.

[edit] Harrumph. Wikipedia says that only three-and-a-bit volumes have yet been published. Seven volumes was the original plan. Smacks a little of George R. R. Martin?

Another way to thing theory of programming logic is a general understanding of language logic for which I recommend https://www.amazon.com/Philosophy-Language-P-Martinich/dp/01...

I am going through that book myself right now. It came to me highly recommended. I don’t have a computer science degree.

Going way back in computing, often an important issue was, how fast will a program run? That study is now sometimes called computational time complexity.

This study was important because, for some common work, some ways of programming the work ran many times faster than some other ways -- i.e., the study of computational time complexity got some big results.

Usually in practice an issue of a little less concern than running time was how much of the computer main memory would a program need, and this study was computational space complexity.

The first big case of big gains was running time for sorting. So, for some positive integer n, we are given n numbers (or alphabetic names, etc.) and want to sort them into ascending order. So, an obvious first approach is to look at all n numbers one at a time and find the smallest. Then look at the remaining n - 1 numbers and again find the smallest. Then with a little algebra, the running time grows proportional to n^2 (n times n, n squared). So we say (I'm omitting some fine points) that the running time is "big O n^2" written

O(n^2).

Now for some big stuff: (1) There is a way (method, technique, algorithm) called heap sort with running time (computational time complexity)

O(n log(n) )

both on average for random numbers and also for the worst case of the order of the given n numbers. (2) Heap sort works by comparing numbers two at a time (so did our

O(n^2)

algorithm above), and there is a cute counting result from A. Gleason, long a math prof at Harvard, that shows that for sorting by comparing numbers two at a time

O(n log(n) )

is the fastest possible. (3) Heap sort is also in-place which means that the storage used, except for a constant independent of n, is just what is needed for the n numbers being sorted.

After sorting, there was interest in working with trees. Likely the tree most people are most familiar with is the hierarchical file system. A tree can be good for keeping a set of numbers in order while adding numbers to the set or removing numbers from the set. To get good guaranteed fast running time, we want the tree balanced, that is, all the paths in the tree from the root to the leaves are about the same length. So, keeping the tree balanced while making the changes and doing so with relatively fast worst case running time was a challenge. One solution was AVL trees (see D. Knuth's The Art of Computer Programming: Sorting and Searching or more recent books listed in this thread) and, mostly for data stored on disk, B-trees. Actually there are several important, that is, relatively fast, algorithms for manipulating trees.

Early on in computing there were more problems with algorithms that improved running time, e.g., string searching.

There is a general technique, dynamic programming, that is the basis of several important, relatively fast algorithms. Here the programming is in the sense of the English project planning, that is, from the field of optimization in operations research.

Generally, given a program, it can be difficult to do algebraic manipulations, say, assuming either random or worst case inputs, to find the "Big O" running time. Knuth's book starts with a lot of algebraic techniques that can help finding Big O running times. That work can be as challenging as we please.

There is some work that early on was not really in computer science but very much needs computers and where running time was and is a huge issue. An important source of such work was optimization in operations research. The first work of concern was the simplex algorithm of linear programming. Next was the closely related integer linear programming, i.e., combinatorial optimization. There were too many cases of problems starting with n numbers and running in

O(2^n)

which is exponential