Essential Discrete Mathematics for Computer Science
When I accepted to write this review, I did not pay much attention to the endorsements appearing in the back cover, because after all they look simply as ads trying to sell the book. Now, after reading the whole book, I looked back at them and I must say that I fully agree with their statements, so I also want to convince all of you to get this book, read and enjoy it as much as I did in the past weeks.
The authors have managed to pack in about 400 pages all the material that I would expect in a discrete mathematics textbook at this level, including all of the following:
- Proof techniques and induction,
- Sets, relations, and functions,
- Propositional and quantificational logic,
- Directed and undirected graphs,
- Finite automata and regular languages,
- Order notation and complexity of algorithms,
- Basic combinatorics,
- Recurrence relations,
- Discrete probability, and
- Modular arithmetic and public key cryptography.
Since other textbooks cover similar material in more than one thousand denser pages, it is clear that the treatment cannot be so exhaustive and some other things have to be excluded (for example, the number of proposed exercises in each chapter of the reviewed textbook is smaller than in other textbooks on the same subject), and hence the contents faithfully correspond to the “essential” idea in the title. The book provides a comprehensive introduction to really all the essential concepts that a student of Computer Science must learn in order to understand the foundations of the discipline.
The textbook is written as to be self contained, requiring little algebra and calculus in the way of prerequisites, but this does not mean that it forgets about mathematical rigor; on the contrary, it begins by introducing proof techniques and then emphasizes mathematical reasoning throughout the whole development (as the authors insist at the beginning, almost all results are proved in detail), together with enough intuition to make the explanations very clear. This is also accomplished by including computing motivations which, in addition to helping the student to understand the concepts, provide a global view of the subject that otherwise can be seen as a set of disconnected pieces. Furthermore, the text is very well written and I have only found three errata and a misplaced definition in 400 pages, which is quite difficult to accomplish. The first author is already very well-known for, among other things, excellent textbooks such as “Elements of the Theory of Computation” with C. Papadimitriou, but here he has put at work all his experience combined with the software engineering expertise of the second author, and both of them together have managed to produce a remarkable textbook that is a pleasure to read; for this reason, it is also perfect for self-study at any level.
Although the contents of this textbook do not fit exactly the syllabus of the discrete mathematics course in my school (where more logic is included in this course at the same time that probability is taught in another mathematics course, while automata and algorithm complexity deserve a separate course each), I have already told my colleagues teaching the discrete mathematics course that this textbook should be included as supplementary material, and at the same time I have ordered some copies for our library. Because, as I said at the beginning of this review, I want to share with everybody my enjoyment of this excellent textbook.