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:
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.
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
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