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

1. Algorithms, Numbers, and Machines

This chapter begins with a strange algorithm, Russian Peasant Multiplication, that may or may not work correctly. (Verifying correctness is a constant theme throughout this book, and the techniques used to decide such issues are explained thoroughly later.)
The concept of an algorithm is illustrated by more examples: testing primes, factoring an integer into primes, and finding the greatest common divisor of two integers. Representation of numbers in computers is discussed, and truncation error is shown to be an unavoidable consequence of using machines to do computation.
This chapter ends with an algorithm to solve equations, that is, to find a numerical solution that is accurate to any degree one might desire. This illustrates the formal idea of the limit of a sequence in the context of how many iterations must be done by the algorithm to guarantee a specified accuracy.
Tom Jenkyns, Ben Stephenson

2. Sets, Sequences, and Counting

Sets and sequences are the fundamental objects of study in discrete mathematics, and this chapter provides a review of naïve set theory. Formulas for counting sequences, subsets, and permutations are developed, followed by an algorithmic method for counting when no formula applies (or is obvious). The final section looks at infinite sequences, particularly complexity functions of algorithms.
Tom Jenkyns, Ben Stephenson

3. Boolean Expressions, Logic, and Proof

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

4. Searching and Sorting

This chapter explores two very practical problems: searching and sorting. We consider Linear Search and (two versions of) Binary Search. Binary trees are used to describe the search process. Binary search is much, much better but requires sorted input. We give examples of several sorting strategies: selection sorts, exchange sorts, and partition sorts. A binary tree produces a lower bound on the number of key comparisons that must be done in a worst case and in the average case.
This chapter ends with timing comparisons and a relation between the time and number of key comparisons that anticipates the notion of order of complexity.
Tom Jenkyns, Ben Stephenson

5. Graphs and Trees

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

6. Relations: Especially on (Integer) Sequences

The two objectives of this chapter are (1) to provide an ordering of sequences of objects so they can be sorted, like individual numbers, and so any finite set of them can be generated in a natural order from the first to the last, and (2) to provide a mechanism for classifying complexity functions by their rates of growth.
Relations in general are defined, then equivalence relations, then order relations.
Relations on sequences of numbers are given, in particular Lexicographic-Order. Relations on infinite sequences of real numbers (including complexity functions of algorithms) are then covered with Big-Oh, Big-Theta, and Little-Oh notation.
Tom Jenkyns, Ben Stephenson

7. Sequences and Series

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

8. Generating Sequences and Subsets

Algorithms are devised to generate lists of objects in Lexicographic-Order: k-sequences on {1..n}, all nonempty subsets of {1..n}, k-subsets of {1..n}, full permutations, and k-permutations on {1..n}. We include calculations of average-case complexity because in each case the average cost is less than 2 or 3 operations no matter how big k and n are.
Tom Jenkyns, Ben Stephenson

9. Discrete Probability and Average-Case Complexity

Discrete probability is introduced as a method to estimate average cases, not to predict individual outcomes from a process subject to chance or unpredictability, like flipping a coin or rolling a die.
Basic definitions are given for the fundamental concepts: an experiment, a sample space, a probability function, events, independent events, conditional probability, random variables, and the expected value of a random variable. Expected value generalizes average value and is used for calculating the average-case complexity of algorithms.
Standard distributions, which are good models of many real-world processes including computer applications, are treated in some detail. These include the uniform distribution, the binomial distribution, and the geometric distribution.
This chapter ends with a proof that the average-case complexity of QuickSort is O(nlgn).
Tom Jenkyns, Ben Stephenson

10. Turing Machines

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