Book Review: Mathematics for Computer Science (Suggestion for MIRI Research Guide)

Contents

  Introduction
  Prerequisites
  Comparison to Other Discrete Math Texts
    Rosen
    Concrete Mathematics
    Epp
    Coverage
  Complaints
    A Note on Printing
  Final Thoughts
  Acknowledgements
None
5 comments

tl;dr: I read Mathematics for Computer Science (MCS) and found it excellent. I sampled Discrete Mathematics and Its Applications (Rosen)—currently recommended in MIRI's research guide—as well as Concrete Mathematics and Discrete Mathematics with Applications (Epp), which appear to be MCS's competition. Based on these partial readings, I found MCS to be the best overall text. I therefore recommend MIRI change the recommendation in its research guide.

Introduction

MCS is used at MIT for their introductory discrete math course, 6.042, which appears to be taken primarily by second-semester freshman and sophomores. You can find OpenCourseWare archives from 2010 and 2015, although the book is self-contained; I never had occasion to use them throughout my reading. 

Prerequisites

The only prerequisite is single-variable calculus. In particular, I noted integration, differentiation, and convergence/infinite sums coming up. That said, I don't remember seeing them coming up in sections that provided a lot of dependencies: with just a first course in algebra, I feel a smart 14-year-old could get through 80–90% of the book, albeit with some help, mostly in places where "do a bunch of algebra" steps are omitted. An extra 4–5 years of practice doing algebraic manipulations makes a difference.

MCS is also an introduction to proofwriting. In my experience, writing mathematical proofs is a skill complex enough to require human feedback to get all the nuances of why something works and why something else doesn't work and why one approach is better than another. If you've never written proofs before and would like a human to give you feedback, please pm me.

Comparison to Other Discrete Math Texts

Rosen

I randomly sampled section 4.3 of Rosen, on primes and greatest common divisors and was very unimpressed. Rosen states the fundamental theorem of arithmetic without a proof. The next theorem had a proof which was twice as long and half as elegant as it could have been. The writing was correct but unmotivating and wordy. For instance, Rosen writes "If n is a composite integer", which is redundant, since all composite numbers are integers, so he could have just said "If n is composite".

In the original Course Recommendations for Friendliness Researchers, Louie responded to Rosen's negative reviews:

people taking my recommendations would be geniuses by-and-large and that the harder book would be better in the long-run for the brightest people who studied from it.

Based on the sample I read, Rosen is significantly dumbed-down relative to MCS. Rosen does not prove the fundamental theorem of arithmetic whereas MCS proves it in section 9.4. For the next theorem, Rosen gives an inelegant proof when a much sleeker—but reasonably evident!—proof exists, making it feel like Rosen expected the reader to not be able to follow the sleeker proof. Rosen's use of "composite integer" instead of "composite" seems like he assumes the reader doesn't understand that the only objects one describes as composite are integers; MCS does not contain the string "composite integer".

In the section I read, Rosen has worked examples for finding gcd(24, 36) and gcd(17, 22), something I remember doing when I was 12. It's almost like Rosen was spoon-feeding how to guess the teacher's password for the student to regurgitate on an exam instead of building insight.

Concrete Mathematics

There are probably individuals who would prefer Concrete Mathematics to MCS. These people are probably into witchcraft.

I explain by way of example. In section 21.1.1, MCS presents a very sleek, but extremely nonobvious, proof of gambler's ruin using a clever argument courtesy of Pascal. In section 21.1.2, MCS gives a proof that doesn't require the reader to be "as ingenuious Pascal [sic]". As an individual who is decidedly not as ingenious as Pascal was, I appreciate this.

More generally, say we want to prove a theorem that looks something like "If A, then B has property C." You start at A and, appealing to the definition of C, show that B has it. There's probably some cleverness involved in doing so, but you start at the obvious place (A), end in the obvious place (B satisfies the definition of C), and don't rely on any crazy, seemingly-unrelated insights. Let's call this sort of proof mundane.

(Note that mundane is far from mechanical. Most of the proofs in Baby Rudin are mundane, but require significant cleverness and work to generate independently.)

There is a virtue in mundane proofs: a smart reader can usually generate them after they read the theorem but before they read its proof. Doing is beneficial, since proof-generating makes the theorem more memorable. It also gives the reader practice building intuition by playing around with the mathematical objects and helps them improve their proofwriting by comparing their output to a maximally refined proof.

On the end of the spectrum opposing mundane is witchcraft. Proofs that use witchcraft typically have a step where you demonstrate you're as ingenious as Pascal by having a seemingly-unrelated insight that makes everything easier. Notice that, even if you are as ingenious as Pascal, you won't necessarily be able to generate these insights quickly enough to get through the text at any reasonable pace.

For the reasons listed above, I prefer mundane proofs. This isn't to say MCS is devoid of witchcraft: sometimes it's the best or only way of getting a proof. The difference is that MCS uses mundane proofs whenever possible whereas Concrete Mathematics invokes witchcraft left and right. This is why I don't recommend it.

Individuals who are readily as ingenious as Pascal, don't want the skill-building benefits of mundane proofs, or prefer the whimsy of witchcraft may prefer Concrete Mathematics.

Epp

I randomly sampled section 12.2 of Epp and found it somewhat dry but wholly unobjectionable. Unlike Rosen, I felt like Epp was writing for an intelligent human being (though I was reading much further along in the book, so maybe Rosen assumed the reader was still struggling with the idea of proof). Unlike Concrete Mathematics, I detected no witchcraft. However, I felt that Epp had inferior motivation and was written less engagingly. Epp is also not licensed under Creative Commons.

Coverage

Epp, Rosen, and MCS are all ~1000 pages long, whereas Concrete Mathematics is ~675. To determine what these books covered that might not be in MCS, I looked through their table of contents' for things I didn't recognize. The former three have the same core coverage, although Epp and Rosen go into material you would find in Computability and Logic or Sipser (also part of the research guide), whereas MCS spends more time developing discrete probability. Based on the samples I read, Epp and MCS have about the same density, whereas Rosen spends little time building insight and a lot of time showing how to do really basic, obvious stuff. I would expect Epp and MCS to have roughly the same amount of content covering mostly (but not entirely) the same stuff and Rosen to offer a mere shadow of the insight of the other two.

Concrete Mathematics seems to contain a subset of MCS's topics, but from the sections I read, I expect the presentation to be wildly different.

Complaints

My only substantial complaint about MCS is that, to my knowledge, the source LaTeX is not available. Contrast this to SICP, which has the HTML available. This resulted in a proliferation of PDFs tailored for different use cases. It'd be nice, for instance, to have a print-friendly version of MCS (perhaps with fewer pages), plus a version that fit nicely onto the small screen of an ereader or mobile device, plus a version with the same aspect ratio as my monitor. This all would be extremely easy to generate given the source. It would also facilitate crowdsourcing proofreading: there are more than a few typos, although they don't preempt comprehension. At the very least, I wish there were somewhere to submit errata.

Some parts of MCS were notation-heavy. To quote what a professor once wrote on a problem set of mine:

I'm not sure all the notation actually serves the goal of clarifying the argument for the reader. Of course, such notation is sometimes needed. But when it is not needed, it can function as a tool with which to bludgeon the reader…

I found myself referring to Wikipedia's glossary of graph theory terms more than a few times when I was making definitions to put into Anki. Not sure if this is measuring a weak section or a really good glossary or something else.

A Note on Printing

A lot of people like printed copies of their books. One benefit of MCS I've put forward is that it's free (as in beer), so I investigated how much printing would cost.

I checked the local print shops and Kinko's online was unable to find printing under $60, a typical price around $70, with the option to burn $85 if I wanted nicer paper. This was more than I had expected and between ⅓ and ½ (ish) the price of Rosen or Epp.

Personally, I think printing is counterproductive, since the PDF has clickable links.

Final Thoughts

Despite sharing first names, I am not Richard Stallman. I prefer the license on MCS to the license on its competitors, but I wouldn't recommend it unless I thought the text itself was superior. I would recommend baby Rudin (nonfree) over French's Introduction to Real Analysis; Hoffman and Kunze's Linear Algebra (nonfree) over Jim Hefferson's Linear Algebra; and Epp over 2010!MCS. The freer the better, but that consideration is trumped by the quality of the text. When you're spending >100 hours working out of a book that provides foundational knowledge for the rest of your life, ~$150 and a loss of freedom is a price many would pay for better quality.

Eliezer writes:

Tell a real educator about how Earth classes are taught in three-month-sized units, and they would’ve sputtered and asked how you can iterate fast enough to learn how to teach that.

Rosen is in its seventh edition. Epp is in its fourth edition and Concrete Mathematics its second. The earliest copy of MCS I've happened across comes from 2004. Near as I can tell, it is improved every time the authors go through the material with their students, which would put it in its 25th edition.

And you know what? It's just going to keep getting better faster than anything else.

Acknowledgements

Thank you to Gram Stone for reviewing drafts of this review.

5 comments

Comments sorted by top scores.