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

tl;dr: I read Math­e­mat­ics for Com­puter Science (MCS) and found it ex­cel­lent. I sam­pled Discrete Math­e­mat­ics and Its Ap­pli­ca­tions (Rosen)—cur­rently recom­mended in MIRI’s re­search guide—as well as Con­crete Math­e­mat­ics and Discrete Math­e­mat­ics with Ap­pli­ca­tions (Epp), which ap­pear to be MCS’s com­pe­ti­tion. Based on these par­tial read­ings, I found MCS to be the best over­all text. I there­fore recom­mend MIRI change the recom­men­da­tion in its re­search guide.

Introduction

MCS is used at MIT for their in­tro­duc­tory dis­crete math course, 6.042, which ap­pears to be taken pri­mar­ily by sec­ond-semester fresh­man and sopho­mores. You can find OpenCourseWare archives from 2010 and 2015, al­though the book is self-con­tained; I never had oc­ca­sion to use them through­out my read­ing.

If you liked Com­putabil­ity and Logic (re­view), cur­rently in the MIRI re­search guide, you’ll like MCS:
MCS is a won­der­ful book. It’s well writ­ten. It’s rigor­ous, but does a nice job of mo­ti­vat­ing the ma­te­rial. It effi­ciently proves a num­ber of coun­ter­in­tu­itive re­sults and then helps you see them as in­tu­itively ob­vi­ous. Freed from the con­straint of print­ing cost, it con­tains many di­a­grams which are gen­er­ally use­ful. You can find the pdf here or, if that link breaks, by googling “Math­e­mat­ics for Com­puter Science”. (See sec­tion 21.2 for why this works.)
MCS is reg­u­larly up­dated dur­ing the semester. Based on the dates of re­vi­sion given to the cover, I sus­pect that the au­thors at­tempt to up­date it within a week of the last up­date dur­ing the semester. The cur­rent ver­sion is 87 pages longer than the 2015 ver­sion, sug­gest­ing ~40 pages of ma­te­rial is added a year. My fa­vorite thing about the con­stant up­dates was that I never needed to dou­ble check state­ments about our cur­rent state of knowl­edge to see if any­thing had changed since pub­li­ca­tion.
MCS is li­censed un­der a Creative Com­mons at­tri­bu­tion share-al­ike li­cense: it is free in the sense of both beer and free­dom. I’m a big fan of such copy­left li­censes, so I give MIT ma­jor props. I’ve tried to re­main un­bi­ased in my re­view, but halo effect sug­gests my views on the text might be af­fected by the text’s li­cense: salt ac­cord­ingly.

Prerequisites

The only pre­req­ui­site is sin­gle-vari­able calcu­lus. In par­tic­u­lar, I noted in­te­gra­tion, differ­en­ti­a­tion, and con­ver­gence/​in­finite sums com­ing up. That said, I don’t re­mem­ber see­ing them com­ing up in sec­tions that pro­vided a lot of de­pen­den­cies: with just a first course in alge­bra, 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 alge­bra” steps are omit­ted. An ex­tra 4–5 years of prac­tice do­ing alge­braic ma­nipu­la­tions makes a differ­ence.

MCS is also an in­tro­duc­tion to proofwrit­ing. In my ex­pe­rience, writ­ing math­e­mat­i­cal proofs is a skill com­plex enough to re­quire hu­man feed­back to get all the nu­ances of why some­thing works and why some­thing else doesn’t work and why one ap­proach is bet­ter than an­other. If you’ve never writ­ten proofs be­fore and would like a hu­man to give you feed­back, please pm me.

Com­par­i­son to Other Discrete Math Texts

Rosen

I ran­domly sam­pled sec­tion 4.3 of Rosen, on primes and great­est com­mon di­vi­sors and was very unim­pressed. Rosen states the fun­da­men­tal the­o­rem of ar­ith­metic with­out a proof. The next the­o­rem had a proof which was twice as long and half as el­e­gant as it could have been. The writ­ing was cor­rect but un­mo­ti­vat­ing and wordy. For in­stance, Rosen writes “If n is a com­pos­ite in­te­ger”, which is re­dun­dant, since all com­pos­ite num­bers are in­te­gers, so he could have just said “If n is com­pos­ite”.

In the origi­nal Course Recom­men­da­tions for Friendli­ness Re­searchers, Louie re­sponded to Rosen’s nega­tive re­views:

peo­ple tak­ing my recom­men­da­tions would be ge­niuses by-and-large and that the harder book would be bet­ter in the long-run for the bright­est peo­ple who stud­ied from it.

Based on the sam­ple I read, Rosen is sig­nifi­cantly dumbed-down rel­a­tive to MCS. Rosen does not prove the fun­da­men­tal the­o­rem of ar­ith­metic whereas MCS proves it in sec­tion 9.4. For the next the­o­rem, Rosen gives an in­el­e­gant proof when a much sleeker—but rea­son­ably ev­i­dent!—proof ex­ists, mak­ing it feel like Rosen ex­pected the reader to not be able to fol­low the sleeker proof. Rosen’s use of “com­pos­ite in­te­ger” in­stead of “com­pos­ite” seems like he as­sumes the reader doesn’t un­der­stand that the only ob­jects one de­scribes as com­pos­ite are in­te­gers; MCS does not con­tain the string “com­pos­ite in­te­ger”.

In the sec­tion I read, Rosen has worked ex­am­ples for find­ing gcd(24, 36) and gcd(17, 22), some­thing I re­mem­ber do­ing when I was 12. It’s al­most like Rosen was spoon-feed­ing how to guess the teacher’s pass­word for the stu­dent to re­gur­gi­tate on an exam in­stead of build­ing in­sight.

Con­crete Mathematics

There are prob­a­bly in­di­vi­d­u­als who would pre­fer Con­crete Math­e­mat­ics to MCS. Th­ese peo­ple are prob­a­bly into witchcraft.

I ex­plain by way of ex­am­ple. In sec­tion 21.1.1, MCS pre­sents a very sleek, but ex­tremely nonob­vi­ous, proof of gam­bler’s ruin us­ing a clever ar­gu­ment cour­tesy of Pas­cal. In sec­tion 21.1.2, MCS gives a proof that doesn’t re­quire the reader to be “as in­genuious Pas­cal [sic]”. As an in­di­vi­d­ual who is de­cid­edly not as in­ge­nious as Pas­cal was, I ap­pre­ci­ate this.

More gen­er­ally, say we want to prove a the­o­rem that looks some­thing like “If A, then B has prop­erty C.” You start at A and, ap­peal­ing to the defi­ni­tion of C, show that B has it. There’s prob­a­bly some clev­er­ness in­volved in do­ing so, but you start at the ob­vi­ous place (A), end in the ob­vi­ous place (B satis­fies the defi­ni­tion of C), and don’t rely on any crazy, seem­ingly-un­re­lated in­sights. Let’s call this sort of proof mun­dane.

(Note that mun­dane is far from me­chan­i­cal. Most of the proofs in Baby Rudin are mun­dane, but re­quire sig­nifi­cant clev­er­ness and work to gen­er­ate in­de­pen­dently.)

There is a virtue in mun­dane proofs: a smart reader can usu­ally gen­er­ate them af­ter they read the the­o­rem but be­fore they read its proof. Do­ing is benefi­cial, since proof-gen­er­at­ing makes the the­o­rem more mem­o­rable. It also gives the reader prac­tice build­ing in­tu­ition by play­ing around with the math­e­mat­i­cal ob­jects and helps them im­prove their proofwrit­ing by com­par­ing their out­put to a max­i­mally re­fined proof.

On the end of the spec­trum op­pos­ing mun­dane is witchcraft. Proofs that use witchcraft typ­i­cally have a step where you demon­strate you’re as in­ge­nious as Pas­cal by hav­ing a seem­ingly-un­re­lated in­sight that makes ev­ery­thing eas­ier. No­tice that, even if you are as in­ge­nious as Pas­cal, you won’t nec­es­sar­ily be able to gen­er­ate these in­sights quickly enough to get through the text at any rea­son­able pace.

For the rea­sons listed above, I pre­fer mun­dane proofs. This isn’t to say MCS is de­void of witchcraft: some­times it’s the best or only way of get­ting a proof. The differ­ence is that MCS uses mun­dane proofs when­ever pos­si­ble whereas Con­crete Math­e­mat­ics in­vokes witchcraft left and right. This is why I don’t recom­mend it.

In­di­vi­d­u­als who are read­ily as in­ge­nious as Pas­cal, don’t want the skill-build­ing benefits of mun­dane proofs, or pre­fer the whimsy of witchcraft may pre­fer Con­crete Math­e­mat­ics.

Epp

I ran­domly sam­pled sec­tion 12.2 of Epp and found it some­what dry but wholly un­ob­jec­tion­able. Un­like Rosen, I felt like Epp was writ­ing for an in­tel­li­gent hu­man be­ing (though I was read­ing much fur­ther along in the book, so maybe Rosen as­sumed the reader was still strug­gling with the idea of proof). Un­like Con­crete Math­e­mat­ics, I de­tected no witchcraft. How­ever, I felt that Epp had in­fe­rior mo­ti­va­tion and was writ­ten less en­gag­ingly. Epp is also not li­censed un­der Creative Com­mons.

Coverage

Epp, Rosen, and MCS are all ~1000 pages long, whereas Con­crete Math­e­mat­ics is ~675. To de­ter­mine what these books cov­ered that might not be in MCS, I looked through their table of con­tents’ for things I didn’t rec­og­nize. The former three have the same core cov­er­age, al­though Epp and Rosen go into ma­te­rial you would find in Com­putabil­ity and Logic or Sipser (also part of the re­search guide), whereas MCS spends more time de­vel­op­ing dis­crete prob­a­bil­ity. Based on the sam­ples I read, Epp and MCS have about the same den­sity, whereas Rosen spends lit­tle time build­ing in­sight and a lot of time show­ing how to do re­ally ba­sic, ob­vi­ous stuff. I would ex­pect Epp and MCS to have roughly the same amount of con­tent cov­er­ing mostly (but not en­tirely) the same stuff and Rosen to offer a mere shadow of the in­sight of the other two.

Con­crete Math­e­mat­ics seems to con­tain a sub­set of MCS’s top­ics, but from the sec­tions I read, I ex­pect the pre­sen­ta­tion to be wildly differ­ent.

Complaints

My only sub­stan­tial com­plaint about MCS is that, to my knowl­edge, the source LaTeX is not available. Con­trast this to SICP, which has the HTML available. This re­sulted in a pro­lifer­a­tion of PDFs tai­lored for differ­ent use cases. It’d be nice, for in­stance, to have a print-friendly ver­sion of MCS (per­haps with fewer pages), plus a ver­sion that fit nicely onto the small screen of an ereader or mo­bile de­vice, plus a ver­sion with the same as­pect ra­tio as my mon­i­tor. This all would be ex­tremely easy to gen­er­ate given the source. It would also fa­cil­i­tate crowd­sourc­ing proofread­ing: there are more than a few ty­pos, al­though they don’t pre­empt com­pre­hen­sion. At the very least, I wish there were some­where to sub­mit er­rata.

Some parts of MCS were no­ta­tion-heavy. To quote what a pro­fes­sor once wrote on a prob­lem set of mine:

I’m not sure all the no­ta­tion ac­tu­ally serves the goal of clar­ify­ing the ar­gu­ment for the reader. Of course, such no­ta­tion is some­times needed. But when it is not needed, it can func­tion as a tool with which to blud­geon the reader…

I found my­self refer­ring to Wikipe­dia’s glos­sary of graph the­ory terms more than a few times when I was mak­ing defi­ni­tions to put into Anki. Not sure if this is mea­sur­ing a weak sec­tion or a re­ally good glos­sary or some­thing else.

A Note on Printing

A lot of peo­ple like printed copies of their books. One benefit of MCS I’ve put for­ward is that it’s free (as in beer), so I in­ves­ti­gated how much print­ing would cost.

I checked the lo­cal print shops and Kinko’s on­line was un­able to find print­ing un­der $60, a typ­i­cal price around $70, with the op­tion to burn $85 if I wanted nicer pa­per. This was more than I had ex­pected and be­tween ⅓ and ½ (ish) the price of Rosen or Epp.

Per­son­ally, I think print­ing is coun­ter­pro­duc­tive, since the PDF has click­able links.

Fi­nal Thoughts

De­spite shar­ing first names, I am not Richard Stal­l­man. I pre­fer the li­cense on MCS to the li­cense on its com­peti­tors, but I wouldn’t recom­mend it un­less I thought the text it­self was su­pe­rior. I would recom­mend baby Rudin (non­free) over French’s In­tro­duc­tion to Real Anal­y­sis; Hoff­man and Kunze’s Lin­ear Alge­bra (non­free) over Jim Heffer­son’s Lin­ear Alge­bra; and Epp over 2010!MCS. The freer the bet­ter, but that con­sid­er­a­tion is trumped by the qual­ity of the text. When you’re spend­ing >100 hours work­ing out of a book that pro­vides foun­da­tional knowl­edge for the rest of your life, ~$150 and a loss of free­dom is a price many would pay for bet­ter qual­ity.

Eliezer writes:

Tell a real ed­u­ca­tor about how Earth classes are taught in three-month-sized units, and they would’ve sput­tered and asked how you can iter­ate fast enough to learn how to teach that.

Rosen is in its sev­enth edi­tion. Epp is in its fourth edi­tion and Con­crete Math­e­mat­ics its sec­ond. The ear­liest copy of MCS I’ve hap­pened across comes from 2004. Near as I can tell, it is im­proved ev­ery time the au­thors go through the ma­te­rial with their stu­dents, which would put it in its 25th edi­tion.

And you know what? It’s just go­ing to keep get­ting bet­ter faster than any­thing else.

Acknowledgements

Thank you to Gram Stone for re­view­ing drafts of this re­view.