Just saw this old thread thanks to the spammers! Updated https://intelligence.org/research-guide/ based on this suggestion.
Thanks for the review! I definitely had the sense that Rosen was doing a lot of hand holding and handwaving - it's certainly a very introductory text. I've read both Rosen and Eppstein and actually found Rosen better. The discrete math class I took in college used Scheinerman's Mathematics: A Discrete Introduction, which I also found to be worse than Rosen.
At the time I actually really enjoyed the fact that Rosen went on tangents and helped me learn how to write a proof, since I was relatively lacking in mathematical maturity. I'd add that Rosen does cover proof writing earlier in the book, but I suspect that MCS might do this job better. Given the target audience of the MIRI research guide, I think it makes sense to switch over to MCS from Rosen.
I don't think how one could think he or she can sample just one chapter out of a huge book and make a definitive statement about it.
I personally read Susan Epp's book very thoroughly and read a few chapters in Rosen's book. When it comes to the difficulty of contents and the amount of discrete mathematics involved, Rosen's text is way above Epp's. Epp's book is very clearly explained but assumes very little from readers. Therefore, it covers very elementary contents.
While I agree that MCS is a great book filled with great content, I highly discourage anyone to use it for a self-study purpose. It doesn't include any solution. Unless, you already have some mathematical maturity gained from several pure maths courses, the book will not help you much.
Rosen's text is actually at the sweet spot between Epp's text and books like Concrete maths. It will serve most of CS students very well. After this course, they can always pick some chapters from books like MCS and benefit from it.
Thanks. I was going to start Concrete Mathematics, but your review has convinced me to take MCS—I have no love for witchcraft.
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.
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.
I'm skeptical that this is a huge problem in practice,and my hunch is that this is mostly a matter of the original proof being badly conveyed. In the case of Pascal ingenuious proof of the gambler's ruin, what the exposition in MCS isn't conveying clearly enough is that we're essentially defining a "game" (or more subtly, a valuation) as f([gambler's capital]) that is fair in the expectation sense, and, more importantly, results in "ruin" or "win" exactly when the original game does. If you start with a proof of this statement, you're back in the familiar pattern of "If A, then B has property C". We've just inserted a simple step of "Actually, we'll just need to show that B' has property C, and then B does too", which is mundane, because it just follows from what C is like!
The point though is that not all expositions make this obvious enough; some just focus on proofs that are "mundane" in your original sense, but this too is a kind of "dumbing down" and lack of mathematical maturity.
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.
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.
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.
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.
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.
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.
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.
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 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.
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.
Thank you to Gram Stone for reviewing drafts of this review.