Contentsviii
- “mcs” — 2015/5/18 — 1:43 — page ii — #
- “mcs” — 2015/5/18 — 1:43 — page iii — #
- Introduction I Proofs
- 0.1 References
- 1 What is a Proof?
- 1.1 Propositions
- 1.2 Predicates
- 1.3 The Axiomatic Method
- 1.4 Our Axioms
- 1.5 Proving an Implication
- 1.6 Proving an “If and Only If”
- 1.7 Proof by Cases
- 1.8 Proof by Contradiction
- 1.9 GoodProofs in Practice
- 1.10 References
- 2 The Well Ordering Principle
- 2.1 Well Ordering Proofs
- 2.2 Template for Well Ordering Proofs
- 2.3 Factoring into Primes
- 2.4 Well Ordered Sets
- 3 Logical Formulas
- 3.1 Propositions from Propositions
- 3.2 Propositional Logic in Computer Programs
- 3.3 Equivalence and Validity
- 3.4 The Algebra of Propositions
- 3.5 The SAT Problem
- 3.6 Predicate Formulas
- 3.7 References
- 4 Mathematical Data Types
- 4.1 Sets
- 4.2 Sequences
- 4.3 Functions
- 4.4 Binary Relations
- 4.5 Finite Cardinality
- “mcs” — 2015/5/18 — 1:43 — page iv — #
- 5 Induction Contentsiv
- 5.1 Ordinary Induction
- 5.2 Strong Induction
- 5.3 Strong Induction vs. Induction vs. Well Ordering
- 5.4 State Machines
- 6 Recursive Data Types
- 6.1 Recursive Definitions and Structural Induction
- 6.2 Strings of Matched Brackets
- 6.3 Recursive Functions on Nonnegative Integers
- 6.4 Arithmetic Expressions
- 6.5 Induction in Computer Science
- 7 Infinite Sets
- 7.1 Infinite Cardinality
- 7.2 The Halting Problem
- 7.3 The Logic of Sets
- 7.4 Does All This Really Work?
- Introduction II Structures
- 8 Number Theory
- 8.1 Divisibility
- 8.2 The Greatest Common Divisor
- 8.3 Prime Mysteries
- 8.4 The Fundamental Theorem of Arithmetic
- 8.5 Alan Turing
- 8.6 Modular Arithmetic
- 8.7 Remainder Arithmetic
- 8.8 Turing’s Code (Version 2.0)
- 8.9 Multiplicative Inverses and Cancelling
- 8.10 Euler’s Theorem
- 8.11 RSA Public Key Encryption
- 8.12 What has SAT got to do with it?
- 8.13 References
- 9 Directed graphs & Partial Orders
- 9.1 Vertex Degrees
- 9.2 Walks and Paths
- “mcs” — 2015/5/18 — 1:43 — page v — #
- 9.3 Adjacency Matrices Contentsv
- 9.4 Walk Relations
- 9.5 Directed Acyclic Graphs & Scheduling
- 9.6 Partial Orders
- 9.7 Representing Partial Orders by Set Containment
- 9.8 Linear Orders
- 9.9 Product Orders
- 9.10 Equivalence Relations
- 9.11 Summary of Relational Properties
- 10 Communication Networks
- 10.1 Complete Binary Tree
- 10.2 Routing Problems
- 10.3 Network Diameter
- 10.4 Switch Count
- 10.5 Network Latency
- 10.6 Congestion
- 10.7 2-D Array
- 10.8 Butterfly
- 10.9 Beneˇs Network
- 11 Simple Graphs
- 11.1 Vertex Adjacency and Degrees
- 11.2 Sexual Demographics in America
- 11.3 Some Common Graphs
- 11.4 Isomorphism
- 11.5 Bipartite Graphs & Matchings
- 11.6 The Stable Marriage Problem
- 11.7 Coloring
- 11.8 Simple Walks
- 11.9 Connectivity
- 11.10 Forests & Trees
- 11.11 References
- 12 Planar Graphs
- 12.1 Drawing Graphs in the Plane
- 12.2 Definitions of Planar Graphs
- 12.3 Euler’s Formula
- 12.4 Bounding the Number of Edges in a Planar Graph
- 12.5 Returning toK 5 andK3;3
- 12.6 Coloring Planar Graphs
- “mcs” — 2015/5/18 — 1:43 — page vi — #
- 12.7 Classifying Polyhedra Contentsvi
- 12.8 Another Characterization for Planar Graphs
- Introduction III Counting
- 12.9 References
- 13 Sums and Asymptotics
- 13.1 The Value of an Annuity
- 13.2 Sums of Powers
- 13.3 Approximating Sums
- 13.4 Hanging Out Over the Edge
- 13.5 Products
- 13.6 Double Trouble
- 13.7 Asymptotic Notation
- 14 Cardinality Rules
- 14.1 Counting One Thing by Counting Another
- 14.2 Counting Sequences
- 14.3 The Generalized Product Rule
- 14.4 The Division Rule
- 14.5 Counting Subsets
- 14.6 Sequences with Repetitions
- 14.7 Counting Practice: Poker Hands
- 14.8 The Pigeonhole Principle
- 14.9 Inclusion-Exclusion
- 14.10 Combinatorial Proofs
- 14.11 References
- 15 Generating Functions
- 15.1 Infinite Series
- 15.2 Counting with Generating Functions
- 15.3 Partial Fractions
- 15.4 Solving Linear Recurrences
- 15.5 Formal Power Series
- 15.6 References
- “mcs” — 2015/5/18 — 1:43 — page vii — #
- Introduction IV Probability
- 16 Events and Probability Spaces
- 16.1 Let’s Make a Deal
- 16.2 The Four Step Method
- 16.3 Strange Dice
- 16.4 The Birthday Principle
- 16.5 Set Theory and Probability
- 16.6 References
- 17 Conditional Probability
- 17.1 Monty Hall Confusion
- 17.2 Definition and Notation
- 17.3 The Four-Step Method for Conditional Probability
- 17.4 Why Tree Diagrams Work
- 17.5 The Law of Total Probability
- 17.6 Simpson’s Paradox
- 17.7 Independence
- 17.8 Mutual Independence
- 18 Random Variables
- 18.1 Random Variable Examples
- 18.2 Independence
- 18.3 Distribution Functions
- 18.4 Great Expectations
- 18.5 Linearity of Expectation
- 19 Deviation from the Mean
- 19.1 Markov’s Theorem
- 19.2 Chebyshev’s Theorem
- 19.3 Properties of Variance
- 19.4 Estimation by Random Sampling
- 19.5 Confidence versus Probability
- 19.6 Sums of Random Variables
- 19.7 Really Great Expectations
- 20 Random Walks
- 20.1 Gambler’s Ruin
- 20.2 Random Walks on Graphs
- “mcs” — 2015/5/18 — 1:43 — page viii — #
- Introduction V Recurrences
- 21 Recurrences
- 21.1 The Towers of Hanoi
- 21.2 Merge Sort
- 21.3 Linear Recurrences
- 21.4 Divide-and-Conquer Recurrences
- 21.5 A Feel for Recurrences
- Bibliography
- Glossary of Symbols
- Index