8
$\begingroup$

I am a mathematician but I would like to learn basics of computer science. I have seen many books that are fine but has some mistakes. For example, Introduction to algorithms even says that one should use $f(n)\in O(g(n))$ but still uses the notation $f(n)= O(g(n))$.

Is there university level computer science books that are suitable for person who wants to study computer science on very rigorous books, or that are aimed to mathematician?

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ welcome to Computer Science Educators! A very nice question. I advise you use the resource-request tag. $\endgroup$
    – ItamarG3
    Jul 29, 2017 at 9:31
  • 7
    $\begingroup$ Those answering are encouraged to do more than name a book. Say why you believe the book is a good fit, and describe it to some extent. One book per answer is likely better than a single long list. $\endgroup$
    – Buffy
    Jul 29, 2017 at 12:50
  • $\begingroup$ I already gave one answer (SICP), but, if I could give a second, I might suggest Computers and Intractability. en.wikipedia.org/wiki/Computers_and_Intractability $\endgroup$
    – Ellen Spertus
    Jul 29, 2017 at 21:29
  • 1
    $\begingroup$ @EllenSpertus As I understand it, in situations like this, the limit is one "resource" per answer, with appropriate supporting text to clarify why it's recommended and how it fits the question. I don't recall anything limiting it to one answer per user, however. Even on non-list questions a second answer is acceptable, as long as it is distinct from the first one, as they must be, by definition, in this case. Write up the answer supporting Computers and Intractability. $\endgroup$
    – Gypsy Spellweaver
    Jul 30, 2017 at 1:12
  • $\begingroup$ @GypsySpellweaver I had not realized I could give multiple answers. I'll do so. $\endgroup$
    – Ellen Spertus
    Jul 30, 2017 at 22:53

4 Answers 4

Reset to default
7
$\begingroup$

The Art of Computer Programming in four volumes by Knuth is an obvious choice.

The first chapter of the first volume is a pretty solid course in discrete mathematics all by itself. If you can do all of the problems in that chapter you can earn a PhD in CS. (Some of the problems remain unsolved, I think - at least they were when the book was first published.)

Knuth is a Mathematician turned Computer Scientist and gives the mathematician's view of the field about as well as anyone can. You can depend on the accuracy of the book as the author has induced the community to drive out all inaccuracies using bounties.

Improve this answer
$\endgroup$
8
  • 2
    $\begingroup$ ob xkcd: xkcd.com/163 $\endgroup$
    – Ellen Spertus
    Jul 29, 2017 at 17:52
  • $\begingroup$ Someone without your mathematical background might start with Knuth's Concrete Mathematics. $\endgroup$
    – Ellen Spertus
    Jul 29, 2017 at 17:52
  • 1
    $\begingroup$ While those are excellent books, they are nigh impossible to read cover-to-cover, even for seasoned academics, yet alone students. If using this, be sure you pick small, self-contained sections and make sure beforehand that the students have all the preliminary knowledge required for understanding the chapters. Knuth is excellent if you want to go really deep, but the amount of time you need to spend on each single page to properly understand it is very high. $\endgroup$
    – ComicSansMS
    Aug 4, 2017 at 8:15
  • $\begingroup$ @Ellen Spertus: "Someone without your mathematical background" The OP is a mathematician. $\endgroup$
    – beroal
    Sep 10, 2017 at 11:31
  • $\begingroup$ @beroal I know. I was saying that the OP could skip Concrete Mathematics but others might find it useful background. $\endgroup$
    – Ellen Spertus
    Sep 10, 2017 at 14:40
4
$\begingroup$

In addition to Knuth, I would recommend the classic Structure and Interpretation of Computer Programming by Abelson and Sussman. It covers such topics as:

  • Writing simple programs that do powerful things,
  • Blurring the lines between data and code, including functions as first-class objects,
  • Creating little languages to solve problems,
  • Writing an interpreter,

and much more.

It is one of the most loved and respected CS books. See also:

Note that the text, in various formats (original HTML, HTML5, PDF), is available for free online, as are video lectures by the authors.

Improve this answer
$\endgroup$
2
  • $\begingroup$ IMHO, this book is not rigorous enough for a mathematician. There are no theorems, no proofs. $\endgroup$
    – beroal
    Sep 10, 2017 at 11:42
  • $\begingroup$ @beroal it depends what the OP wants to learn. Not all of computer science is theorems and proofs. SICP is considered the deepest introduction to programming, which is part of computer science. $\endgroup$
    – Ellen Spertus
    Sep 10, 2017 at 14:49
2
$\begingroup$

The Semantics of Programming Languages is an important and very mathematical subject. Great strides have been made in the past 20 or so years. One book that stands out is A Theory of Objects by Luca Cardelli and Martín Abadi

Luca, especially, is an expert in operational semantics. He presents a generalized operational calculus for analyzing all aspects of object-oriented languages. The book is deep, but essential for those wanting a deep understanding of the underlying principles of OO languages and, perhaps, wanting to design future languages.

Language is more than syntax. It is the semantics that lets the student form proper hypotheses about programs and programming.

Most compilers are still "syntax directed" but Peter Lee, in his doctoral dissertation (U of Michigan). shows how a compiler can be built from the semantics instead.

Improve this answer
$\endgroup$
0
$\begingroup$

Another classic is Computers and Intractability: A Guide to the Theory of NP-Completeness by Garey and Johnson. As you may know, NP (which stands for "nondeterministic polynomial time") refers to a set of problems that are computationally very difficult but whose answers can be checked in polynomial time relative to the size of their input. Whether all such problems can be solved in polynomial time (P=NP?) is one of the greatest unsolved questions in computer science.

Garey and Johnson (as the book is referred to) is about NP-Complete problems, members of NP to which all other members of NP could be reduced. The book catalogs problems known to be NP-complete, including proofs that they are members, usually reductions from other NP-complete problems.

Published in 1979, the book is somewhat outdated but is still regarded as a classic [3]. (Google Scholar lists about 60,000 citations.) The introduction (available online), in which an employee explains to their boss why they can't provide a simple solution to a problem, is also classic.

Disclaimer: I am not a theoretical computer scientist. I welcome comments from any.

Improve this answer
$\endgroup$

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.