Book Review: Discrete Mathematics and Its Applications (MIRI Course List)

Fol­low­ing in the path of So8res and oth­ers, I’ve de­cided to work my way through the text­books on the MIRI Re­search Guide. I’ve been work­ing my way through the guide since last Oc­to­ber, but this is my first re­view. I plan on fol­low­ing up this re­view with re­views of En­der­ton’s A Math­e­mat­i­cal In­tro­duc­tion to Logic and Sipser’s In­tro­duc­tion to the The­ory of Com­pu­ta­tion. Hope­fully these re­views will be of some use to you.

Discrete Math­e­mat­ics and Its Applications

Discrete Math­e­mat­ics and Its Ap­pli­ca­tions is won­der­ful, gen­tle in­tro­duc­tion to the math needed to un­der­stand most of the other books on the MIRI course list. It suc­cess­fully pulls off a col­lo­quial tone of voice. It spends a lot of time mo­ti­vat­ing con­cepts; it also con­tains a lot of in­ter­est­ing trivia and short bi­ogra­phies of fa­mous math­e­mat­i­ci­ans and com­puter sci­en­tists (which the text­book calls “links”). Ad­di­tion­ally, the book pro­vides a lot of ex­am­ples for each of its the­o­rems and top­ics. It also fleshes out the key sub­jects (count­ing, proofs, graphs, etc.) while also pro­vid­ing a high level overview of their ap­pli­ca­tions. Th­ese com­bine to make it an ex­cel­lent first text­book for learn­ing dis­crete math­e­mat­ics.

How­ever, for much the same rea­sons, I would not recom­mend it nearly as much if you’ve taken a dis­crete math course. Peo­ple who’ve par­ti­ci­pated in math com­pe­ti­tions at the high school level prob­a­bly won’t get much out of the text­books ei­ther. Even though I went in with only the dis­crete math I did in high school, I still got quite frus­trated at times be­cause of how long the book would take to get to the point. Discrete Math­e­mat­ics is in­tended to be quite in­tro­duc­tory and it suc­ceeds in this goal, but it prob­a­bly won’t be very suit­able as any­thing other than re­view for read­ers be­yond the in­tro­duc­tory level. The sole ex­cep­tion is the last chap­ter (on mod­els of com­pu­ta­tion), but I recom­mend pick­ing up a more com­pre­hen­sive overview from Sipser’s The­ory of Com­pu­ta­tion in­stead.

I still highly recom­mend it for those not fa­mil­iar with the top­ics cov­ered in the book. I’ve sum­ma­rized the con­tents of the text­book be­low:

Con­tents:

1. The Foun­da­tions: Logic and Proofs

2. Ba­sic Struc­tures: Sets, Func­tions, Se­quences, Sums, and Matrices

3. Algorithms

4. Num­ber The­ory and Cryptography

5. In­duc­tion and Recursion

6. Counting

7. Discrete Probability

8. Ad­vanced Count­ing Techniques

9. Relations

10. Graphs

11. Trees

12. Boolean Algebra

13. Model­ing Computation

The Foun­da­tions: Logic and Proofs

This chap­ter in­tro­duces propo­si­tional (sen­ten­tial) logic, pred­i­cate logic, and proof the­ory at a very in­tro­duc­tory level. It starts by in­tro­duc­ing the propo­si­tions of propo­si­tional logic (!), then goes on to in­tro­duce ap­pli­ca­tions of propo­si­tional logic, such as logic puz­zles and logic cir­cuits. It then goes on to in­tro­duce the idea of log­i­cal equiv­alence be­tween sen­tences of propo­si­tional logic, be­fore in­tro­duc­ing quan­tifiers and pred­i­cate logic and its rules of in­fer­ence. It then ends by talk­ing about the differ­ent kinds of proofs one is likely to en­counter – di­rect proofs via re­peated modus po­nens, proofs by con­tra­dic­tion, proof by cases, and con­struc­tive and non-con­struc­tive ex­is­tence proofs.

This chap­ter illus­trates ex­actly why this book is ex­cel­lent as an in­tro­duc­tory text. It doesn’t just in­tro­duce the terms, the­o­rems, and defi­ni­tions; it mo­ti­vates them by giv­ing ap­pli­ca­tions. For ex­am­ple, it ex­plains the need for pred­i­cate logic by point­ing out that there are in­fer­ences that can’t be drawn us­ing only propo­si­tional logic. Ad­di­tion­ally, it also ex­plains the com­mon pit­falls for the differ­ent proof meth­ods that it in­tro­duces.

Ba­sic Struc­tures: Sets, Func­tions, Se­quences, Sums, and Matrices

This chap­ter in­tro­duces the differ­ent ob­jects one is likely to en­counter in dis­crete math­e­mat­ics. Most of it seemed pretty stan­dard, with the fol­low­ing ex­cep­tions: func­tions are in­tro­duced with­out refer­ence to re­la­tions; the “car­di­nal­ity of sets” sec­tion pro­vides a high level overview of a lot of set the­ory; and the ma­tri­ces sec­tion in­tro­duces zero-one ma­tri­ces, which are used in the chap­ters on re­la­tions and graphs.

Algorithms

This chap­ter pre­sents … sur­prise, sur­prise… al­gorithms! It starts by in­tro­duc­ing the no­tion of al­gorithms, and gives a few ex­am­ples of sim­ple al­gorithms. It then spends a page in­tro­duc­ing the halt­ing prob­lem and show­ing its un­de­cid­abil­ity. (!) After­wards, it in­tro­duces big-o, big-omega, and big-theta no­ta­tion and then gives a (very in­for­mal) treat­ment of a por­tion of com­pu­ta­tion com­plex­ity the­ory. It’s quite un­usual to see al­gorithms be­ing dealt with so early into a dis­crete math course, but it’s quite im­por­tant be­cause the au­thor starts pro­vid­ing ex­am­ples of al­gorithms in al­most ev­ery chap­ter af­ter this one.

Num­ber The­ory and Cryptography

This sec­tion goes from sim­ple mod­u­lar ar­ith­metic (3 di­vides 12!) to RSA, which I found ex­tremely im­pres­sive. (Ad­mit­tedly, I’ve only ever read one other dis­crete math text­book.) After in­tro­duc­ing the no­tion of di­visi­bil­ity, the text­book takes the reader on a rapid tour through base-n no­ta­tion, the fun­da­men­tal the­o­rem of ar­ith­metic, the in­fini­tude of primes, the Eu­clidean GCD al­gorithm, Be­zout’s the­o­rem, the Chi­nese re­main­der the­o­rem, Fer­mat’s lit­tle the­o­rem, and other key re­sults of num­ber the­ory. It then gives sev­eral ap­pli­ca­tions of num­ber the­ory: hash func­tions, pseu­do­ran­dom num­bers, check digits, and cryp­tog­ra­phy. The last of these gets its own sec­tion, and the book spends a large amount of it in­tro­duc­ing RSA and its ap­pli­ca­tions.

In­duc­tion and Recursion

This chap­ter in­tro­duces math­e­mat­i­cal in­duc­tion and re­cur­sion, two ex­tremely im­por­tant con­cepts in com­puter sci­ence. Proofs by math­e­mat­i­cal in­duc­tion, ba­si­cally, are proofs that show that a prop­erty is true of the first nat­u­ral num­ber (pos­i­tive in­te­ger in this book), and if it is true of an in­te­ger k it is true of k+1. With these two re­sults, we can con­clude that the prop­erty is true of all nat­u­ral num­bers (pos­i­tive in­te­gers). The book then goes on to in­tro­duce strong in­duc­tion and re­cur­sively defined func­tions and sets. From this, the book then goes on to in­tro­duce the con­cept of struc­tural in­duc­tion, which is a gen­er­al­iza­tion of in­duc­tion to work on re­cur­sively-defined sets. Then, the book in­tro­duces re­cur­sive al­gorithms, most no­tably the merge sort, be­fore giv­ing a high level overview of pro­gram ver­ifi­ca­tion tech­niques.

Counting

The book now changes sub­jects to talk about ba­sic count­ing tech­niques, such as the product rule and the sum rule, be­fore (in­ter­est­ingly) mov­ing on to the pi­geon­hole prin­ci­ple. It then moves on to per­mu­ta­tions and com­bi­na­tions, while in­tro­duc­ing the no­tion of com­bi­na­to­rial proof, which is when we show that two sides of the iden­tity count the same things but in differ­ent ways, or that there ex­ists a bi­jec­tion be­tween the sets be­ing counted on ei­ther side. The text­book then in­tro­duces bino­mial co­effi­cients, Pas­cal’s tri­an­gle, and per­mu­ta­tions/​com­bi­na­tions with rep­e­ti­tion. Fi­nally, it gives al­gorithms that gen­er­ate all the per­mu­ta­tions and com­bi­na­tions of a set of n ob­jects.

Com­pared to other sec­tions, I feel that a higher pro­por­tion of read­ers would be fa­mil­iar with the re­sults of this chap­ter and the one on dis­crete prob­a­bil­ity that fol­lows it. Other than the last sec­tion, which I found quite in­ter­est­ing but not par­tic­u­larly use­ful, I felt like I barely got any­thing from the chap­ter.

Discrete Probability

In this sec­tion the book cov­ers prob­a­bil­ity, a topic that most of LessWrong should be quite fa­mil­iar with. Like most in­tro­duc­tory text­books, it be­gins by in­tro­duc­ing the no­tion of sam­ple spaces and events as sets, be­fore defin­ing prob­a­bil­ity of an event E as the ra­tio of the car­di­nal­ity of E to the car­di­nal­ity of S. We are then in­tro­duced to other key con­cepts in prob­a­bil­ity the­ory: con­di­tional prob­a­bil­ities, in­de­pen­dence, and ran­dom vari­ables, for ex­am­ple. The text­book takes care to flesh out this sec­tion with a dis­cus­sion about the Birth­day Prob­lem and Monte Carlo al­gorithms. After­wards, we are treated to a sec­tion on Bayes the­o­rem, with the canon­i­cal ex­am­ple of dis­ease test­ing for rare dis­eases and a less-canon­i­cal-but-still-used-quite-a-lot ex­am­ple of Naïve Bayes spam filters. The chap­ter con­cludes by in­tro­duc­ing the ex­pected value and var­i­ances of ran­dom vari­ables, as well as a lot of key re­sults (lin­ear­ity of ex­pec­ta­tions and Che­by­shev’s Inequal­ity, to list two). Again, aside from the ap­pli­ca­tions, most of this stuff is quite ba­sic.

Ad­vanced Count­ing Techniques

This chap­ter, though ti­tled “ad­vanced count­ing tech­niques”, is re­ally just about re­cur­rences and the prin­ci­ple of in­clu­sion-ex­clu­sion. As you can tell by the length of this sec­tion, I found this chap­ter quite helpful nev­er­the­less.

We be­gin by giv­ing three ap­pli­ca­tions of re­cur­rences: Fibonacci’s “rab­bit prob­lem”, the Tower of Hanoi, and dy­namic pro­gram­ming. We’re then shown how to solve lin­ear ho­moge­nous re­la­tions, which are re­la­tions of the form

an = c1 an-1 + c2 an-2 + … + ck an-k+ F(n)

Where c1, c2, …, ck are con­stants, ck =/​= 0, and F(n) is a func­tion of n. The solu­tions are quite beau­tiful, and if you’re not fa­mil­iar with them I recom­mend look­ing them up. After­wards, we’re in­tro­duced to di­vide-and-con­quer al­gorithms, which are re­cur­sive al­gorithms that solve smaller and smaller in­stances of the prob­lem, as well as the mas­ter method for solv­ing the re­cur­rences as­so­ci­ated with them, which tend to be of the form

f(n) = a f(n/​b) + cnd

After these al­gorithms, we’re in­tro­duced to gen­er­at­ing func­tions, which are yet an­other way of solv­ing re­cur­rences.

Fi­nally, af­ter a long trip through var­i­ous re­cur­rence-solv­ing meth­ods, the text­book in­tro­duces the prin­ci­ple of in­clu­sion-ex­clu­sion, which lets us figure out how many el­e­ments are in the union of a finite num­ber of finite sets.

Relations

Fi­nally, 7 chap­ters af­ter the text­book talks about func­tions, it fi­nally gets to re­la­tions. Re­la­tions are defined as sets of n-tu­ples, but the book also gives al­ter­na­tive ways of rep­re­sent­ing re­la­tions, such as ma­tri­ces and di­rected graphs for bi­nary re­la­tions. We’re then in­tro­duced to tran­si­tive clo­sures and War­shall’s al­gorithm for com­put­ing the tran­si­tive clo­sure of a re­la­tion. We con­clude with two spe­cial types of re­la­tions: equiv­alence re­la­tions, which are re­flex­ive, sym­met­ric, and tran­si­tive; and par­tial or­der­ings, which are re­flex­ive, anti-sym­met­ric, and tran­si­tive.

Graphs

After be­ing first in­tro­duced to di­rected graphs as a way of rep­re­sent­ing re­la­tions in the pre­vi­ous chap­ter, we’re given a much more fleshed out treat­ment in this chap­ter. A graph is defined as a set of ver­tices and a set of edges con­nect­ing them. Edges can be di­rected or undi­rected, and graphs can be sim­ple graphs (with no two edges con­nect­ing the same pair of ver­tices) or multi­graphs, which con­tain mul­ti­ple edges con­nect­ing the same pair of ver­tices. We’re then given a ton of ter­minol­ogy re­lated to graphs, and a lot of the­o­rems re­lated to these terms. The treat­ment of graphs is quite ad­vanced for an in­tro­duc­tory text­book – it cov­ers Dijk­stra’s al­gorithm for short­est paths, for ex­am­ple, and ends with four col­or­ing. I found this chap­ter to be a use­ful re­view of a lot of graph the­ory.

Trees

After deal­ing with graphs, we move on to trees, or con­nected graphs that don’t have cy­cles. The text­book gives a lot of ex­am­ples of ap­pli­ca­tions of trees, such as bi­nary search trees, de­ci­sion trees, and Huff­man cod­ing. We’re then pre­sented with the three ways of travers­ing a tree – in-or­der, pre-or­der, and post-or­der. After­wards, we get to the topic of span­ning trees of graphs, which are trees that con­tain ev­ery ver­tex in the graph. Two al­gorithms are pre­sented for find­ing span­ning trees – depth first search and breadth first search. The chap­ter ends with a sec­tion on min­i­mum span­ning trees, which are span­ning trees with the least weight. Once again we’re pre­sented with two al­gorithms for find­ing min­i­mum span­ning trees: Prim’s Al­gorithm and Kruskal’s al­gorithm. Hav­ing never seen ei­ther of these al­gorithms be­fore, I found this sec­tion to be quite in­ter­est­ing, though they are given a more com­pre­hen­sive treat­ment in most in­tro­duc­tory al­gorithms text­books.

Boolean Algebra

This sec­tion in­tro­duces Boolean alge­bra, which is ba­si­cally a set of rules for ma­nipu­lat­ing el­e­ments of the set {0,1}. Why is this use­ful? Be­cause, as it turns out, Boolean alge­bra is di­rectly re­lated to cir­cuit de­sign! The text­book first in­tro­duces the ter­minol­ogy and rules of Boolean alge­bra, and then moves on to cir­cuits of logic gates and their re­la­tion­ship with Boolean func­tions. We con­clude with two ways to min­i­mize the com­plex­ity of Boolean func­tions (and thus cir­cuits) – Kar­naugh Maps and the Quine-McCluskey Method, which are both quite in­ter­est­ing.

Model­ing Computation

This is the chap­ter of Rosen that I’m pretty sure isn’t cov­ered by most in­tro­duc­tory text­books. In many ways, it’s an ex­tremely con­densed ver­sion of the first cou­ple chap­ters of a the­ory of com­pu­ta­tion text­book. It cov­ers phase struc­ture gram­mars, finite state ma­chines, and closes with Tur­ing ma­chines. How­ever, I found this chap­ter a lot more poorly mo­ti­vated than the rest of the book, and also that Sipser’s In­tro­duc­tion to the The­ory of Com­pu­ta­tion offers a lot bet­ter in­tro­duc­tion to these top­ics.

Who should read this?

If you’re not fa­mil­iar with dis­crete math­e­mat­ics, this is a great book that will get you up to speed on the key con­cepts, at least to the level where you’ll be able to un­der­stand the other text­books on MIRI’s course list. Of the three text­books I’m fa­mil­iar with that cover dis­crete math­e­mat­ics, I think that Rosen is hands down the best. I also think it’s quite a “fun” text­book to skim through, even if you’re fa­mil­iar with some of the top­ics already.

How­ever, I think that peo­ple fa­mil­iar with the top­ics prob­a­bly should look for other books, es­pe­cially if they are look­ing for text­books that are more con­cise. It might also not be suit­able if you’re already re­ally mo­ti­vated to learn the sub­ject, and just want to jump right in. There are a few top­ics not nor­mally cov­ered in other dis­crete math text­books, but I feel that it’s bet­ter to pick up those top­ics in other text­books.

What should I read?

In gen­eral, the rule for the text­book is: read the sec­tions you’re not fa­mil­iar with, and skim the sec­tions you are fa­mil­iar with, just to keep an eye out for cool ex­am­ples or the­o­rems.

In terms of chap­ter-by-chap­ter, chap­ters 1 and 2 seem like they’ll help if you’re new to math­e­mat­ics or proofs, but prob­a­bly can be skipped oth­er­wise. Chap­ter 3 is pretty good to know in gen­eral, though I sus­pect most peo­ple here would find it too easy. Chap­ters 4 through 12 are what most courses on dis­crete math­e­mat­ics seem to cover, and form the bulk of the book – I would recom­mend skim­ming them once just to make sure you know them, as they’re also quite im­por­tant for un­der­stand­ing any se­ri­ous CS text­book. Chap­ter 13, on the other hand, seems kind of tacked on, and prob­a­bly should be picked up in other text­books.

Fi­nal Notes

Of all the books on the MIRI re­search guide, this is prob­a­bly the most ac­cessible, but it is by no means a bad book. I’d highly recom­mend it to any­one who hasn’t had any ex­po­sure to dis­crete math­e­mat­ics, and I think it’s an im­por­tant pre­req­ui­site for the rest of the books on the MIRI re­search guide.