Theoretical CS and Math - self-study recommendations

Problem Detail: 

I am a non-CS grad and my field of study is unrelated to CS. However, as part of a larger plan to become a computer scientist, I want to obtain a solid background in theoretical computer science and math as it relates to CS. I did a plenty of research and selected the following best/really good books on the topic of CS and math and would like to ask for your opinions on:

• Completeness of topics covered (please recommend anything I've missed)
• Overlap of material covered / overkill area (please recommend books that should be removed from the list)
• Order to study the books (I listed in the order that I think they should be studied)

The list feels excessively long, so I would appreciate recommendations to remove some books, without the loss of the core knowledge require for CS.

So, the books are:

1. Mathematician's Delight by W. W. Sawyer
2. How to Prove It: A Structured Approach by Daniel J. Velleman
3. How to Solve It: A New Aspect of Mathematical Method by G. Polya
4. An Introduction to Functional Programming Through Lambda Calculus by Greg Michaelson
5. Foundations of Computer Science by Al Aho and Jeff Ullman (http://i.stanford.edu/~ullman/focs.html)
6. Concrete Mathematics: A Foundation for Computer Science by Graham, Knuth, and Patashnik
7. Introduction to the Theory of Computation by Michael Sipser
8. Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman
9. Computational Complexity: A Conceptual Perspective by Oded Goldreich
10. Computational Complexity: A Modern Approach by Sanjeev Arora, Boaz Barak
11. A Course in Combinatorics by J. H. van Lint, R. M. Wilson
12. Computability: An Introduction to Recursive Function Theory by Nigel Cutland
13. Computers and Intractability: A Guide to the Theory of NP-Completeness by M.R. Garey, D.S. Johnson
14. Theory of Recursive Functions and Effective Computability by Hartley Rogers
15. Inequalities by G.H. Hardy, J. E. Littlewood, G. Polya
16. Mathematical Logic: A Course With Exercises (Part I): Propositional Calculus, Bookean Algebras, Predicate Calculus by René Cori, Daniel Lascar
17. Mathematical Logic: A Course With Exercises (Part II): Recursion Theory, Godel's Theorems, Set Theory, Model Theory by René Cori, Daniel Lascar

Asked By : CSLover

Answered By : Yuval Filmus

Your list is extremely problematic.

To start with, I would flatly skip books 6,11,12,14,15,16,17: Books 6, 11 and 15 are general mathematics which is not really needed unless you become a theoretical researcher. Books 12 and 14 cover recursion theory which is not computer science (even though it deals with computability!). Books 16 and 17 cover advanced topics in logic, whereas you only need to know very basic logic.

Out of books 1,2,3, I would choose just one to serve as a general introduction to mathematics and proofs.

Books 5,7,8,9,10,13 cover several subjects: automata theory, algorithms, and complexity theory. Let me suggest that you follow Sipser (Book 7) for automata theory and complexity theory, and Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein ("CLRS") for algorithms.

Book 4 deals with functional programming. While my computer science education has never included any courses on this subject, it is fair to say that many researchers in theoretical computer science count functional programming as part of the essential foundations.

Summarizing: what you remain with is

• One of books 1-3 (or any comparable "introduction to proof" text)
• CLRS
• Book 4 (functional programming)
• Book 7 (automata theory and complexity theory)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/7334