Most professional computer scientists understand that to be successful in our discipline, students need to learn discrete math. As a result of this understanding, discrete math is a required part of most computer science (CS) curricula. However, CS students who take this class often do not fully appreciate the need for the subject matter; as a result, they miss out on material that is important for future CS classes. One reason for this student attitude is that, while existing discrete math textbooks do give examples of how some of the material is useful in computing, they just as often fail to provide such motivation.
This book is specifically aimed at CS students. The authors include the same discrete math topics that other books have, but, in contrast to most existing books, they introduce each topic with a clear (and entertaining) CS motivation.
I especially liked the beginning of the book, where the authors explain the need for proofs (in other words, for mathematics) by describing two interesting cases: (1) the Russian peasant multiplication algorithm and (2) the cake-cutting problem. In the first case, several examples show that the result of applying this algorithm is indeed the product of the two given numbers. In the second case, in which one selects N points on a circle, connects each pair by a straight line, and counts the number of resulting pieces, the number of pieces is 1 for N = 1, 2 for N = 2, 4 for N = 3, 8 for N = 4, and so on, which looks like doubling. In both cases, a typical student will conclude that both hypotheses have been confirmed by these examples. In the first case, the answer is indeed always the product. However, for cake-cutting, while we do get 16 pieces for N = 5, for N = 6, the number of pieces is smaller than the expected 32. This is clear evidence that testing is not enough, and a formal (that is, mathematical) proof is needed if we want to make sure that an algorithm always produces the correct result. The authors hope that such motivation will entice students to be more eager to learn about proofs.
The book covers the usual discrete math topics: sets, binary numbers, combinatorics, Boolean logic, proofs, graphs and trees (and related algorithms), big-O and little-O notations, and the basics of probability. All these topics are described in a very entertaining way. For example, combinatorial formulas are illustrated with a story about a student who asks two of her boyfriends to bring home a few bananas by selecting from a bunch that has a bad banana.
The book contains topics that CS students normally learn in other required classes, including: basic numerical methods, such as finding a solution to an equation f(x) = 0; computation accuracy (usually taught in numerical math classes); searching and sorting algorithms; worst-case and average-case computational complexity (usually taught in CS courses); and Turing machines (which usually appear in a class on automata).
The book also includes topics not necessarily required for CS majors, such as recurrence equations, which are typically taught in an algorithms class.
Each section is well written, with a highlighted subsection on the most important ideas and plenty of exercises. I highly recommend this book to everyone. It can be used in two different ways. The easiest way is to teach only the topics that are usually taught in discrete math classes (and ignore the other parts of the book). Alternatively, you could cover the whole book and, if needed, rearrange the other classes to avoid duplication. No matter how you use this book, its highly entertaining presentation of the material will undoubtedly make the class a success.
A warning is in order, however: the book’s entertaining style may create a false impression that this material is easy for CS students. It is not easy. It is challenging. That being said, with proper faculty guidance, and the CS motivations given in each math section, students can meet these challenges.
