Re:Ask HN: What are the most fundamental books on computer s...
by einpoklum on Monday October 21, 2019 @10:10AM
(#21312427)
Some of these are quite fundamental but not very popular. Which is good, because people forget those. I'm not much of a Sipser guy but maybe it's because they didn't use it at my alma mater when I took my Theory of Computation and Automata courses.
[ Parent
| on HN ]
Re:Ask HN: What are the most fundamental books on computer s...
by sixstringtheory on Monday October 21, 2019 @12:00PM
(#21313777)
Sipser was the one my alma mater used, so if you could, please post the one you used! I’d be interested in an alternative.
Re:Ask HN: What are the most fundamental books on computer s...
by einpoklum on Tuesday October 22, 2019 @07:56AM
(#21322599)
It was a university-internal booklet written by Prof. Oded Goldreich when he had taught the course in the early 1990s. Don't think it was ever published as a proper book.
See: https://webcourse.cs.technion.ac.il/236343/Spring2004/book.h...
Re:Ask HN: What are the most fundamental books on computer s...
by sixstringtheory on Tuesday October 22, 2019 @12:59PM
(#21325968)
Ah I see. Well in any case, thanks for the link, it led to several books I'm interested to check out...
- 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)
Re:Ask HN: What are the most fundamental books on computer s...
by einpoklum on Tuesday October 22, 2019 @07:11PM
(#21329406)
Papadimitriou is older, but good, in that the Barak-Arora one is huge, I think.
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: