14
$\begingroup$

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
Improve this question
$\endgroup$
7
  • $\begingroup$ Please refer to this question cstheory.stackexchange.com/questions/3253/… $\endgroup$
    – Bartosz Przybylski
    Dec 11, 2012 at 20:09
  • $\begingroup$ Start with a known Algorithm book if you have no experience in this topic yet. $\endgroup$
    – AJed
    Dec 11, 2012 at 20:09
  • $\begingroup$ @Bartek: Thank you, but this was one of the questions I looked at before to compile the list in the first place. My question is more about how to practically read all the great material out there. Time is always a constraint, so I want to know what books I should "not" read to avoid repetition etc. $\endgroup$
    – CSLover
    Dec 11, 2012 at 20:12
  • $\begingroup$ @AJed: Are you suggesting to start with book #5 on the list instead of some of the math books #1-4? I believe #5 gives a gentle intro to algorithms and data structures. $\endgroup$
    – CSLover
    Dec 11, 2012 at 20:14
  • $\begingroup$ Too much here. I'd just pick one and go, then worry about what comes next when you get there. I might recommend Sipser to start for a beginner who wants a solid background in foundations of CS. $\endgroup$
    – usul
    Dec 11, 2012 at 20:22

3 Answers 3

Reset to default
10
$\begingroup$

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)
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you SO much for such a thorough response. I knew the list was excessive, but reading all kinds of book recommendations for computer scientists, you end up with a long list. Your recommendation is very practical, and that is what I am after. Big thank you!! $\endgroup$
    – CSLover
    Dec 11, 2012 at 20:41
  • 1
    $\begingroup$ I disagree with the advice that "math is not needed". Pick any aspect of computer science and I will show you how math is needed. The more math you learn, the better you're off. On the other hand, it is almost impossible to learn real math on one's own, without going to school. So you are probably better off concentrating on computer science, that is easier to learn. $\endgroup$
    – Andrej Bauer
    Dec 12, 2012 at 1:03
5
$\begingroup$

You might also consider taking advantage of some of the many online courses available. For example, both Stanford and MIT offer (free) online courses in computer science, and I think there are many others available as well.

As far as books go, I second most of Yuval's recommendations, except that CLRS is a great reference, but a little overwhelming as an introductory book to just sit down and read through. For a first pass at the algorithms portion, I might recommend Algorithms by Dasgupta et al.. The previous link is to the free online pre-print, but it's also pretty cheap to buy in paperback.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ok. I appreciate your response. Thank you very much. $\endgroup$
    – CSLover
    Dec 11, 2012 at 21:17
2
$\begingroup$

The references you are suggesting would make a "very" theoretical computer scientist. but I honestly dont find any benefit reading all these books if you are from a non-CS degree. This of course all depends on what you need.

I find some books such as Book 14, 15, 16, 17 are not intended to computer scientists. Book 3 is verbose. It is just general for any student. Therefore I assume book 1 and 2 are the same.

For me - being in your same situation as not originally a computer scientist (but instead an electrical/computer engineer) - I propose two initial directions:

  • algorithms design and analysis, (many people suggest the CLRS Introduction to Algorithms. It is a great reference, but I am really not a fan of it and initially it was a bet harder to understand it and sometimes very verbose. I suggest though that you follow its table of contents, and from there you check online courses for clearer references).

--- make sure to master a programming language to IMPLEMENT the algorithms and data structures you learn - therefore, I suggest the series of Algorithms, of Sedgewick (amazing !)

--- ADDED: I also suggest this book: Combinatorial Algorithms: Generation, Enumeration, and Search by D. Kreher. This is a very nice book. Will give you a different prespective to many issues in algorithms.

  • combinatorics (especially graph theory), A Course in Combinatorics by J. H. van Lint, R. M. Wilson, is good. There exist many other references. Usually any well-known combinatorics book is enough - everything else you'd get from additional references from the internet. I personally liked: peter j cameron combinatorics, and Bondy and Murty Graph Theory.

  • a bet of probability (always necessary). It is striking that many fields in science do not use probability. But believe me, all you have to know are the basics.

Then: Many researchers calling themselves theoretical computer scientists focuses so much on theory of computation (automota and others). There are some good books for this (See Yuvul Filmus post),

Aho and Ullman is good (actually all books of Ullman are good). Make yourself comfortable with compiler design (see http://infolab.stanford.edu/~ullman/ullman-books.html).

After that: it all depends on what you want to do. Different directions you can take: 1) databases, 2) pattern recognition and data mining, 3) distributed algorithms, 4) foundation of programming languages, 4) randomize algorithms, and many others. [each of which requires another post] but try to have an idea about all !

*The general idea: if you are new to CS, then make yourself comfortable with as many CS sub-domains as possible. Restricting yourself to "theory" will make you lose much of CS creativity ! * (my opinion)

Improve this answer
$\endgroup$
5
  • $\begingroup$ For me functional programming. Dont use a legacy book like the one you cited. Functional languages are required currently in the industry. There exist some tutorials in the Internet about languages such as Scheme, Haskel and Erlang. Dont get very theoritical, this is my advice. $\endgroup$
    – AJed
    Dec 12, 2012 at 0:51
  • $\begingroup$ All good comments. My goal is to design a complete self-study program and this question only deals with a section of the program, which I thought was the most challenging to organize. Other areas include: Data structures & algorithms, Computer Architecture, Operating Systems, Networking, Security & Cryptography, Parallelism, Formal Methods, Artificial Intelligence, Graphics & Simulation, Databases, Programming Languages, Compilers, software engineering, and finally Unix philosophy & administration. Most of these I think are pretty fundamental to CS, but would warrant a separate question $\endgroup$
    – CSLover
    Dec 12, 2012 at 14:42
  • $\begingroup$ Your best trick is a strong foundation in algorithm design and analysis. -- every other field is a sub-field of algorithms design and analysis. $\endgroup$
    – AJed
    Dec 12, 2012 at 18:47
  • $\begingroup$ Would you be kind and clarify which Sedgewick algorithms book you recommended? He has one called "Algorithms" but it's not a series. He also has "Algorithms in C++" (or other languages) which is 2 books I believe with a total of 5 parts. $\endgroup$
    – CSLover
    Dec 12, 2012 at 18:56
  • $\begingroup$ The one i used were the C++ ones. I used them as references, though. This is his website cs.princeton.edu/~rs $\endgroup$
    – AJed
    Dec 12, 2012 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.