Discrete Mathematics: A Foundation for Computer Science

by David Mix Barrington

Brief Table of Contents

• Chapter 1: Sets, Propositions, and Predicates
  • 1.1 Sets
  • 1.2 Strings and String Operations
  • 1.3 Excursion: What Is A Proof?
  • 1.4 Propositions and Boolean Operations
  • 1.5 Set Operations and Propositions About Sets
  • 1.6 Truth-Table Proofs
  • 1.7 Rules For Propositional Proofs
  • 1.8 Propositional Proof Strategies
  • 1.9 Excursion: A Murder Mystery
  • 1.10 Predicates
  • 1.11 Excursion: Translating Predicates

• Chapter 2: Quantifiers and Predicate Calculus
  • 2.1 Relations
  • 2.2 Excursion: Relational Databases
  • 2.3 Quantifiers
  • 2.4 Excursion: Translating Quantifiers
  • 2.5 Operations on Languages
  • 2.6 Proofs with Quantifiers
  • 2.7 Excursion: Practicing Proofs
  • 2.8 Properties of Binary Relations
  • 2.9 Functions
  • 2.10 Partial Orders
  • 2.11 Equivalence Relations

• Chapter 3: Number Theory
  • 3.1 Divisibility and Primes
  • 3,2 Excursion: Playing With Numbers
  • 3,3 Modular Arithmetic
  • 3.4 There Are Infinitely Many Primes
  • 3.5 The Chinese Remainder Theorem
  • 3.6 The Fundamental Theorem of Arithmetic
  • 3.7 Excursion: Expressing Predicates in Number Theory
  • 3.8 The Ring of Congruence Classes
  • 3.9 Finite Fields and Modular Exponentiation
  • 3.10 Excursion: Certificates of Primality
  • 3.11 The RSA Cryptosystem

• Chapter 4: Recursion and Proof By Induction
  • 4.1 Recursive Definition
  • 4.2 Excursion: Recursive Algorithms
  • 4.3 Proof By Induction for Naturals
  • 4.4 Variations on Induction for Naturals
  • 4.5 Excursion: Fibonacci Numbers
  • 4.6 Proving the Basic Facts of Arithmetic
  • 4.7 Strings and String Operations
  • 4.8 Excursion: Naturals and Strings
  • 4.9 Graphs and Paths
  • 4.10 Trees and Lisp Lists
  • 4.11 Induction for Problem Solving

• Chapter 5: Regular Expressions and Other Recursive Systems
  • 5.1 Regular Expressions and Their Languages
  • 5.2 Examples of Regular Languages
  • 5.3 Excursion: Designing Regular Expressions
  • 5.4 Proving Regular Language Identities
  • 5.5 Proving Properties of the Regular Languages
  • 5.6 Excursion: Hofstadter's MU-Puzzle
  • 5.7 Recursion and Induction in General
  • 5.8 Top-Down and Bottom-Up Definitions
  • 5.9 Excursion: Parsing Arithmetic Expressions
  • 5.10 A Recursive Definition of Imperative Programs
  • 5.11 Correctness of Imperative Programs

• Chapter 6: Fundamental Counting Problems
  • 6.1 Counting: Sum and Product Rules
  • 6.2 Double-Counting and Inclusion/Exclusion
  • 6.3 Counting Sequences (First Counting Problem)
  • 6.4 Counting Permutations (Second Counting Problem)
  • 6.5 Excursion: The Problem of Sorting
  • 6.6 Counting Subsets of a Set (Third Counting Problem)
  • 6.7 Counting Multisets (Fourth Counting Problem)
  • 6.8 Excursion: Listing Permutations and Combinations
  • 6.9 Counting Strings in Languages
  • 6.10 Counting Balanced Strings of Parentheses
  • 6.11 Excursion: Catalan Numbers

• Chapter 7: Further Topics in Combinatorics
  • 7.1 Recurrences
  • 7.2 Solving Some Recurrences
  • 7.3 Excursion: Calculus on Sequences
  • 7.4 Generating Functions
  • 7.5 Asymptotic Notation
  • 7.6 Analysis of Sorting
  • 7.7 Excursion: Selection Problems
  • 7.8 Cardinality of Infinite Sets
  • 7.9 Diagonalization and Uncountability
  • 7.10 Excursion: Ordinal Arithmetic
  • 7.11 Combinatorial Games

• Chapter 8: Graphs
  • 8.1 Graph Definitions
  • 8.2 Adjacency Matrices
  • 8.3 Paths and Matrix Powering
  • 8.4 Excursion: Min-Plus Matrix Powering
  • 8.5 Dynamic Programming
  • 8.6 Euler and Hamilton Paths
  • 8.7 Excursion: Classifying Graphs
  • 8.8 Vertex and Edge Colorings
  • 8.9 Graph Planarity
  • 8.10 Excursion: Euler's Formula for Polyhedra
  • 8.11 Trees as Graphs

• Chapter 9: Trees and Searching
  • 9.1 Trees and Their Uses
  • 9.2 Excursion: Boolean Expressions
  • 9.3 Recursion on Trees
  • 9.4 General Search Trees
  • 9.5 General Breadth-First and Depth-First Search
  • 9.6 BFS and DFS on Graphs
  • 9.7 Excursion: Middle-First Search and Matrices
  • 9.8 Uniform-Cost Search
  • 9.9 A^* Search
  • 9.10 Games and Adversary Search
  • 9.11 Excursion: Hexapawn

• Chapter 10: Discrete Probability
  • 10.1 Probability Distributions
  • 10.2 Expected Value
  • 10.3 Evaluating Games
  • 10.4 Excursion: Analysis of Craps
  • 10.5 Variance and Standard Deviation
  • 10.6 The Binomial Distribution
  • 10.7 Excursion: Election Polling
  • 10.8 The Coupon Collector's Problem
  • 10.9 The Markov and Chebyshev Bounds
  • 10.10 Excursion: Contention Resolution
  • 10.11 The Union Bound

• Chapter 11: Reasoning About Uncertainty
  • 11.1 Conditional Probability and Bayes' Theorem
  • 11.2 Odds and Likelihood
  • 11.3 Examples of Bayesian Reasoning
  • 11.4 Excursion: A Police Lineup
  • 11.5 The Naive Bayes Classifier
  • 11.6 Problems With the Naive Classifier
  • 11.7 Graphical Models of Distributions
  • 11.8 Excursion: A Probabilistic Murder Mystery
  • 11.9 Pseudorandom Generators
  • 11.10 Monte Carlo Simulation
  • 11.11 Excursion: Simulating Baseball Seasons

• Chapter 12: Markov Processes and Classical Games
  • 12.1 Finite-State Random Processes
  • 12.2 Markov Chains
  • 12.3 Limiting Behavior of Markov Chains
  • 12.4 Excursion: Markov Text Generation
  • 12.5 Markov Decision Processes
  • 12.6 Horizons and Discounting
  • 12.7 Value and Policy Iteration
  • 12.8 Excursion: Modeling Blackjack
  • 12.9 Two-Player Simultaneous-Move Games
  • 12.10 Excursion: Modeling Baseball Balls and Strikes
  • 12.11 The Prisoners' Dilemma

• Chapter 13: Graphs
  • 13.1 What Is a Bit?
  • 13.2 Data Compression
  • 13.3 Excursion: Redundancy of English Text
  • 13.4 Variable-Length Codes
  • 13.5 Excursion: Huffman's Algorithm
  • 13.6 Huffman Coding and Entropy
  • 13.7 Error-Detecting Codes
  • 13.8 Error-Correcting Codes
  • 13.9 Excursion: Experimenting With Codes
  • 13.10 Conditional Entropy and Noise
  • 13.11 The Noisy-Channel Theorem

• Chapter 14: Finite-State Machines
  • 14.1 Deterministic Finite Automata
  • 14.2 Proving that DFA's Can't Do Things
  • 14.3 The Myhill-Nerode Theorem
  • 14.4 Excursion: Syntactic Monoids
  • 14.5 Nondeterministic Finite Automata
  • 14.6 The Subset Construction: NFA's into DFA's
  • 14.7 Killing λ-Moves: λ-NFA's into NFA's
  • 14.8 Constructing λ-NFA's from Regular Expressions
  • 14.9 Excursion: Practicing Multiple Constructions
  • 14.10 State Elimination: NFA's into Regular Expressions
  • 14.11 Excursion: Another Way From NFA's to Regular Expressions

• Chapter 15: A Brief Tour of Formal Language Theory
  • 15.1 Two-Way Deterministic Finite Automata
  • 15.2 Grammars, Regular and Otherwise
  • 15.3 Context-Free Languages
  • 15.4 Excursion: Chomsky Normal Form
  • 15.5 CFL's and Pushdown Automata
  • 15.6 Turing Machine Definitions
  • 15.7 Excursion: Unrestricted Grammars
  • 15.8 Turing Machine Semantics
  • 15.9 Excursion: Turing-Hangable Languages
  • 15.10 The Halting Problem and Unsolvability
  • 15.11 A Brief Look at Complexity Theory

Last modified 29 December 2008