Skip to main content
main-content
Top

About this book

This textbook provides an engaging and motivational introduction to traditional topics in discrete mathematics, in a manner specifically designed to appeal to computer science students. The text empowers students to think critically, to be effective problem solvers, to integrate theory and practice, and to recognize the importance of abstraction.
Clearly structured and interactive in nature, the book presents detailed walkthroughs of several algorithms, stimulating a conversation with the reader through informal commentary and provocative questions. Features: no university-level background in mathematics required; ideally structured for classroom-use and self-study, with modular chapters following ACM curriculum recommendations; describes mathematical processes in an algorithmic manner; contains examples and exercises throughout the text, and highlights the most important concepts in each section; selects examples that demonstrate a practical use for the concept in question.

Table of Contents

3. Boolean Expressions, Logic, and Proof

Abstract
The objective of this chapter is to explain the structure of mathematical proofs, especially proofs of correctness of algorithms. Boolean operators are defined by their truth tables. The definition of a valid argument form is intuitive and easily confirmed using a truth table. These are followed by many examples of standard and common patterns of proof: direct and indirect arguments, mathematical induction, and strong mathematical induction.
Tom Jenkyns, Ben Stephenson

5. Graphs and Trees

Abstract
This chapter introduces graphs as diagrams for solving puzzles. Careful definitions specify the language of graph theory: vertices, edges, degrees, paths, circuits, Euler paths, Hamilton paths, and so on. Then our interest returns to trees, with algorithms for depth-first traversal and for breadth-first traversal.
Algorithms for constructing a minimum connector and finding shortest paths joining two specified vertices are given for edge-weighted graphs. Finally, for directed graphs, we give Dijkstra’s Algorithm for shortest dipaths and the Floyd-Warshall Algorithm for the distance matrix.
Tom Jenkyns, Ben Stephenson

7. Sequences and Series

Abstract
Examples of sequences defined by recurrence equations are given and solved. Then, we provide the general method for solving all first-order recurrence equations. The Fibonacci sequence is explored in some depth, followed by the general method for solving second-order recurrence equations. This chapter ends with Zeno’s paradoxes and the formal definition of convergence of infinite series.
Tom Jenkyns, Ben Stephenson

10. Turing Machines

Abstract
This final chapter returns to the topic of the first chapter: What is an algorithm?
We give Alan Turing’s answer to that question and end our story with a disappointing result: namely, that we can prove that there is no algorithm that can solve the halting problem. But this result assures us that machines cannot replace human minds with their creativity and ingenuity.
Tom Jenkyns, Ben Stephenson
Additional information