Moved "Drafty thoughts on what to say" to TextbookPolicy (Thesaurus couldn't come up with a better word for "Policy" and I didn't want to use "Handout". Eww.)
See also Topics2Textbooks for what readings go with what topics.
FoCS Textbooks
- Stuff we sorta know already:
Intro to Algorithms is an awesome book we'll recommend to people who are building their CS library and have the cash. The library will also have a couple copies.
- The complexity stuff is a lot of the same thing between different covers. An interesting thing might be to say, "Find a CS book that covers complexity and automata, don't spend a lot of money on it, they're mostly all the same, but if you're having trouble This One(probably Elements) will work OK," and then have a fun semester getting to know 12 different complexity texts.
Doesn't anyone publish $30 CS textbooks? I mean, seriously...
Minor gripe (to an otherwise perfect Katie): You didn't include pub dates. - las
Additional minor gripe (to an otherwise perfect Katie and Lynn): The only thing that's REALLY useful is ISBN when seeking out textbooks. Looking up anything else online is a real pain. - chris m.
- == With desk copy == Logic books
Logic and Language Models for Computer Science, Hamburger/Richards, Prentice Hall. From TOC, covers logic programming and automata. Amazon prices: $88 new, $50 used. Amazon reviews are horrible, claiming lack of clarity, diagrams.
kmr: Read/skimmed Part I. Sections on logic are good. Once it gets into programming, can be a bit overwordy about Prolog, though it'd probably be a good intro to the language for someone without much programming experience.
Elements of the Theory of Computation, 2nd ed, Lewis/Papadimitriou, Prentice Hall. From TOC, covers languages, automata, complexity. Amazon prices: $90 new, $32 used. Amazon reviews are good.
Theory of Computing: A Gentle Introdution, Kinber/Smith, Prentice Hall. From TOC, covers languages, automata, some complexity. Amazon prices: $90 new, $40 used. Amazon reviews recommend Elements instead but are okay.
Introduction to Automata Theory, Languages, and Computation, 2nd ed, Hopcroft/Motwani/Ullman, Addison Wesley. From TOC, covers proofs, automata, languages(lots), complexity. Amazon prices: $105 new, $28 used.
Introduction to Languages and the Theory of Computation, 3rd ed, John C. Martin, McGraw-Hill. From TOC, covers proofs, automata, complexity. Amazon prices: $137 new, $25 used. Or, $55 new, $37 used, depending on whether you get the Aug 1 edition or the Aug 6 edition. Pah.
Computability and Complexity, 2nd ed, Jones, MIT press. Amazon prices: $70 new, $30 used.
- Probably a bit too advanced for class. (iirc)
Introduction to the Theory of Computation, Michael Sipser. Amazon link. From TOC, covers automata, complexity, glances at logic and languages. Amazon prices: $103 new, $35 used. Amazon reviews are phenomenal.
Consensus: a really well-written textbook for graduate mathematics-level students, ie, beautiful to read, but really dense, probably too advanced for class.
- I actually found this book surprisingly easy to read. It's even easier to read if you have taken or are taking discrete math.
Essentials of Programming Languages, 2nd ed, Friedman/Wand/Haynes, MIT Press. From TOC, covers data abstraction, and interpreters, interpreters, and interpreters. Amazon prices: $51 new, $29 used.
- Lynn says she'll use this herself to get in the mindset for teaching the material, but it's too advanced for class.
Programming Languages: Paradigm and Practice, 2nd ed, Appleby/!VandeKopple, McGraw-Hill. From TOC, covers primitives, abstract data types, imperitive languages, formal languages, declarative languages, and automata. Amazon prices: $103 new, $10 used.
Programming Languages: Principles and Paradigms, Tucker/Noonan, McGraw-Hill.
Algorithms, 1st ed, Johnsonbaugh/Schaefer, Prentice Hall. Amazon prices: $90 new, $43 used.
Introduction to Algorithms, 2nd ed, Cormen/Leiserson/Rivest/Stein, MIT Press. $80 new, $15 used.
- The canonical algs reference book.
- Tucker and Noonan
- Pratt and Zelkowitz
- Gersting (seems to cover automata theory, complexity, analysis of algorithms, logic, graphs, graph algorithms, sorting, etc. -- it's all in there -- but in many cases very shallowly or superficially)
- Rawlins
- Horowitz, Sahni, Rajasekaran
- Sedgewick and Flajolet
- Levitin
- Lewis and Denenberg
- Baase and Van Gelder
Aho and Ullman, Foundations of Computer Science
- Shaffer (2 different versions)