Ask HN: What are the most fundamental books on computer science?
I'm relatively new to CS (4 years) and I've seen a lot of great book recommendations here. But every discipline has it's most fundamental books ... e.g. philosophy -> Socrates, Plato, Aristotle, civil law -> code civil, christianity -> bible, etc. one should read to get a truly deep understanding.
What are those books for CS?
194 comments
[ 3.4 ms ] story [ 306 ms ] threaddon knuth's art of computer programming [if you like some rigor][it is a bit time consuming to read the whole thing , but be sure to atleast try reading the first volume]
2. Like I said elsewhere - TAoCP is an impressive book, but it's certainly not fundamental. It's not used as the "fundament" or foundation of people's CS knowledge.
Computer Systems: A Programmer's Perspective has a lot of good explanations of hardware/os subsystems that can be hard to find detailed explanations of elsewhere. I especially like the sections on virtual memory.
I never took the original 6.001, so my comparison point is actually a stripped-down reincarnation of the original course which is taught by alumni volunteers during the January IAP term. http://web.mit.edu/benmv/6.001/6.184/website/
I think it's more accurate to say that they didn't see a reason to require engineers to learn CS. The class is now completely different. Why python? Not because it's a good programming language, but because there was a library the students could call to control a robot, which was the new goal of the class, not programming.
Here's the quote:
You have to do basic science on your libraries to see how they work, trying out different inputs and seeing how the code reacts. This is a fundamentally different job, and it needed a different course.
So the good thing about the new 6.001 was that it was robot-centered — you had to program a little robot to move around. And robots are not like resistors, behaving according to ideal functions. Wheels slip, the environment changes, etc — you have to build in robustness to the system, in a different way than the one SICP discusses.
And why Python, then? Well, said Sussman, it probably just had a library already implemented for the robotics interface, that was all.
https://www.wisdomandwonder.com/link/2110/why-mit-switched-f...
- Theoretical CS: - Compilers: Principles, Techniques, and Tools (The Dragon Book) - Introduction to the Theory of Computation, Sipser
- Programming: - Java Concurrency In Practice, Brian Goetz - Generics in the Java Programming Language, Gilad Bracha - Professor Frisby's Mostly Adequate Guide to Functional Programming - Unix for Poets - Modern C++
Structure and Interpretation of Computer Programs
Purely Functional Data Structures
Programming in the 1990s
A Logical Approach to Discrete Math
I'm guessing like most people who bought it, it sits collecting dust on the shelf.
Youthful naivety is the only reason I bought it. Completely impenetrable but look, "I'm a real™ software engineer now"
I do least take solace in the fact that the contents of TAOCP are a lot less likely to get stale than the majority of tech books.
I think even Knuth himself would agree here - but it’s also worth going through the implementation yourself once or twice (even if you just throw it away) until you really understand what it’s doing, so that you know what’s most useful when.
I tend to agree, but I'm not completely sure where I'd draw the line between things you have to implement to 'really understand' and things you can just use. ie: I've written hash tables over the years, but I've never written a persistent (think Clojure) style hash table. Maybe I should write one to really understand it? It sounds like fun, and I'd probably learn a lot, but I'm also not at all convinced it would help my effectiveness. The argument becomes even less convincing at larger scales and lower layers. (I don't need to implement a language runtime or SQL database to understand how to use one effectively. Even if, again, both of those sound like a lot of fun and a good way to learn some thing.)
If I had to come up with a general guideline, it would be to encourage developers to be mindful of what's around their layer of the stack and be prepared in the (very unlikely) event to work in one of those layers. But even that's kind of handwavey.
The books are a collection of algorithms and commentary on them. That is not that different from a collection of algorithms in a library.
It's not a page turner where you'll read it from start to finish. It's a resource. As you encounter subjects in computer science and math you can be sure there's a section on it in TAOCP with a deep dive into it.
I pull mine out from time to time when doing research mostly. I've mostly been interested in automated theorem proving, logical databases, etc. Proof search and deductive queries have a lot of moving parts, need to be fast in order to be interactive, and while the book on combinatorics isn't finished yet... the faciles have been amazing.
Yes they do mostly sit there for the most part. But then again so do most of my books. TAOCP is thoroughly researched and hands-down the best resource for a precise treatment of its subjects.
I’ve seen other people suggest that, and I always find it surprising. I did read all of them (well, the first three, anyway) cover to cover, and I can’t imagine trying to jump into the middle without having absorbed all of the preceding material first. The book is so full of back references that even having read everything in order I still found myself turning back to re-read sections that were referred to later. I’m genuinely curious, which sections were you able to make sense of “standalone”?
I don't remember exactly but I've found chapters in the first book on fundamental structures such as trees and sorting algorithms tend to stand well alone.
More recently I've been diving into Book 4, Facile 6 on SAT solvers, combinatorics. I tend to already have some familiarity with the material so it seems to me to stand well on its own.
I really enjoy Knuth's writing style however and appreciate his scrupulousness. The references and indices are top-notch so that if you aren't familiar with the prerequisites they are easily found!
Don't give me too much credit - it took me a little over three years to get through all three of them.
Then I read a Knuth book that really interested me and... there I've got my cheque. Didn't have to read much either, the first word in the first sentence on page Roman One was incorrect. :-)
However I'm now buying & progressing through volume 4 which Knuth is gradually releasing, and it's _way_ more readable, more novel for me (I already learnt my quicksort from more approachable sources, but this contains recent advanced stuff) as well as fun, if you're mathematically inclined.
Knuth still formats algorithms pretty badly IMHO, with little indentation, one-liner loops, "return to step 2" jumps, single-letter names etc. But at least they're not in assembly any longer :-)
This puzzles me from a man who pays tremendous attention to presentation and readability, literally wrote the book on typesetting algorithms & system he devised _for writing this book_, and introduced the idea of literate programming. Surely this is not oversight but very deliberate style, I just don't enjoy it much, but I'd love to learn why he chose it...
It is however in other respects a fantastic example of great technical writing and a great text book.
But as I understand it it's today mostly an extraordinarily great book on inflicting legwounds on yourself.
The book does not try to forewarn you of the myriad pitfalls inherent in C code. Nor does it delve into the language's extended API available via a plethora of internal and external libraries.
What the book does do in only 228 pages is get you up and operational in C as quickly as possible. Then caveat coder.
Personally, I'd like to see more minimalist CS books. I'm tired of having to surf through introductory tomes that often exceed 1000 pages. I'd rather an intro book introduce me to its concepts in as few pages as possible and put the programming advice and copious reference materials elsewhere, like online.
So: Yes, it's more an engineering book. Is that what michalu actually wanted, but didn't know to ask for by the right name?
There are much better books to learn algorithms from. Even Elements of Programming Interviews is better.
It is worth coming back to if you want to read proofs to understand things in depth. But it is terrible as a fundamental instructive text.
Also, I'd add, at least:
Introduction to Algorithms / Cormen, Leiserson & Rivest (and recently also Stein)
Agreed. It's very much like "Feynman's Lectures" in this way.
There are much better resources for philosophy and Christianity, fundamental \neq best
On the other hand, Knuth has an incredible capacity to read, interpret, understand, and especially apply and expand the contents of research papers -- far beyond the capacity of nearly anyone else.
So if you want to spend a lot of time reading through ACM and IEEE journals, have fun. But you'll understand the research and be able to apply it far better when helped by Knuth.
By the way - the same goes for Graham-Knuth-Patashnik's Concrete Mathematics.
Retrieving data is a lot different now than what it was back in the 70s and 80s.
The "searching" section of TAoCP is about search algorithms [0]. Some of these (finding by keys, hashing, etc.) are part of what makes a search engine.
Some parts of what make up a search engine aren't related to searching at all, though. PageRank, for example, is about ranking.
[0] - https://en.wikipedia.org/wiki/Search_algorithm
I now own the second and latest edition of this volume, but it is now over 20 years old. I recommend all of Knuth's publications.
Is Search and Sorting dated? Well, it is quite old. The fold out chart of tape merging patterns for different tape based sorting algorithms doesn't really come up very often anymore. It's been over 40 years since I've had to write programs that worked with mainframe tape drives.
Although AVL trees are covered well, there is no coverage of red-black trees or splay-trees.
Hashing is covered extensively, but there is no discussion of more modern hash table methods (like Cuckoo Hashing or Robin Hood Hashing or the power of choice results).
Furthermore, the basic hardware model used by Knuth in volume 3 assumes uniform costs for memory access. Cache sensitive algorithms aren't considered in volume 3 but are very important today.
Even quicksort, which I learned by studying Volume 3, now has what I consider to be a more modern treatment in Sedgewick and Wayne's Algorithms, 4th Ed.
I found Operating Systems: Three Easy Pieces to be better.
http://pages.cs.wisc.edu/~remzi/OSTEP/
[0] https://news.ycombinator.com/item?id=20729252 (What book to read to get a footing in CS theory?)
It's an extensive and well-rounded look at various fundamental system administration topics with examples included from multiple different *nix distributions (topics like work management, logging, networking, security, the kernel, systemd, permissions, etc.). If you're at all interested in Linux, this is a great book to have on your shelf.
https://admin.com/
It's a book that explores hardware from the ground up. It's one of the most insightful books I've found for getting a real intuition for hardware.
Code Complete by McConnell
I'm not saying that design patterns isn't right for you, but the fact that me and many other programmers avoid it shows that it's not fundamental at all.
Patterns of Enterprise Application Architecture by Martin Fowler.
Domain Driven Design by Eric Evans.
Growing Object-Oriented Software, guided by tests by Steve Freeman and Nat Pryce.
Take civil engineers. Yes they will do some physics but usually only basic stuff in first year. After that they focus more on the higher level systems they will be working with because most working civil engineers will never need anything more advanced than first year physics.
So if the person who posted this Ask HN is not going to do CS research (or the like) then Domain Driven Design might be as fundamental to their education as structural engineering is to a civil engineer. The fact is that nearly all systems that we work with are composed of services/models of some kind. DDD deals with these but more importantly deals with the domain where you can make the most impact as a working engineer (as opposed to a scientist who is like a force multiplier but we need a lot less of them).
"Domain work is messy and demands a lot of complicated new knowledge that doesn’t seem to add to a computer scientist’s capabilities. Instead, the technical talent goes to work on elaborate frameworks, trying to solve domain problems with technology. Learning about and modeling the domain is left to others. Complexity in the heart of software has to be tackled head-on. To do otherwise is to risk irrelevance" - Eric Evans
So the closest parallels are original research papers like Turing's and Shannon's; but you're probably better off reading more recent textbooks.
That said, to balance out the heavy emphasis on programming and engineering books here, some recommendations:
- Sipser. Introduction to the Theory of Computation.
- Russell, Norvig. AI: A Modern Approach.
- For algorithms I don't have a preference. There is Dasgupta-Papadimitriou-Vazirani; Cormen-Leisersen-Rivest-Stein; Kleinberg-Tardos; and more.
A bit farther from core CS, I also like:
- Cover, Thomas. Elements of Information Theory.
- Li, Vitanyi. An Introduction to Kolmogorov Complexity and Its Applications
See: https://webcourse.cs.technion.ac.il/236343/Spring2004/book.h...
- Computers and Intractability: A Guide to the Theory of Np-Completeness
- Computational Complexity (your page has the one by Papadimitriou, but putting it on my Goodreads list led to two others of the same name by Goldreich and Arora/Barak I didn't know of)
Computers and Intractability is a class, it's from 1979. It's most famous for having "the list" of NP complete problems. Obviously not an exhaustive list, but it still merits the definite article :-)
Nowadays this is maintained on-line of course:
https://www.nada.kth.se/~viggo/problemlist/compendium.html
You need to know numbers and simple algebra to tackle trig, you need to know all that to tackle calculus or linear algebra, you need to know those to tackle differential equations.
I would argue CS is closer to philosophy.
Sure you have programming building blocks like variables, loops, conditionals, objects blah blah.
But you quickly head into patterns and conventions that started out as someones opinion on how things should be set up, rather than some fundamental principle.
Mathematics has a linear progression... up until the point at which it branches out into the various subfields.
It very often happens that the shortest, simplest derivation is discovered a century after the original discovery.
E.g. if you define exp(x) as \sum_0^\inf \frac{x^n}{n!}, a crazy amount of things that (historically) took a lot of effort to derive, become exceptionally simple and straightforward.
Now, historically, it didn't make sense to define it that way (especially because limits and infinite sums were only rigourously defined much later). But complexity wise, it is much simpler to first define limits and only then the exponent as an infinite sum.
> But you quickly head into patterns and conventions that started out as someones opinion on how things should be set up, rather than some fundamental principle.
That's not computer science. That is indeed philosophy, specifically software engineering philosophu. Science, it is not.
"The acceleration of the curriculum has had its cost: there has been an accompanying trend to prune away side topics. When I was in high school, for instance, it was standard to study solid geometry and spherical geometry along with plane geometry. These topics have long been abandoned. The shape of the mathematics education of a typical student is tall and spindly. It reaches a certain height above which its base can support no more growth, and there it halts or fails."
source: William Thurston - Mathematical Education https://arxiv.org/pdf/math/0503081.pdf