- “mcs” — 2011/5/9 — 20:49 — page ii — #
- “mcs” — 2011/5/9 — 20:49 — page iii — #
- 1 What is a Proof? I Proofs
- 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
- 2 The Well Ordering Principle
- 2.1 Well Ordering Proofs
- 2.2 Template for Well Ordering Proofs
- 2.3 Summing the Integers
- 2.4 Factoring into Primes
- 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
- 4 Mathematical Data Types
- 4.1 Sets
- 4.2 Sequences
- 4.3 Functions
- 4.4 Binary Relations
- 5 Infinite Sets
- 5.1 Finite Cardinality
- 5.2 Infinite Cardinality
- 5.3 The Halting Problem
- 5.4 The Logic of Sets
- “mcs” — 2011/5/9 — 20:49 — page iv — #
- 5.5 Does All This Really Work? Contentsiv
- 6 Induction
- 6.1 Ordinary Induction
- 6.2 State Machines
- 6.3 Strong Induction
- 6.4 Strong Induction vs. Induction vs. Well Ordering
- 7 Recursive Data Types
- 7.1 Recursive Definitions and Structural Induction
- 7.2 Strings of Matched Brackets
- 7.3 Recursive Functions on Nonnegative Integers
- 7.4 Arithmetic Expressions
- 7.5 Induction in Computer Science
- 8 Number Theory
- 8.1 Divisibility
- 8.2 The Greatest Common Divisor
- 8.3 The Fundamental Theorem of Arithmetic
- 8.4 Alan Turing
- 8.5 Modular Arithmetic
- 8.6 Arithmetic with a Prime Modulus
- 8.7 Arithmetic with an Arbitrary Modulus
- 8.8 The RSA Algorithm
- 8.9 What has SAT got to do with it?
- 9 Directed graphs & Partial Orders II Structures
- 9.1 Digraphs & Vertex Degrees
- 9.2 Digraph Walks and Paths
- 9.3 Adjacency Matrices
- 9.4 Path Relations
- 9.5 Directed Acyclic Graphs & Partial Orders
- 9.6 Weak Partial Orders
- 9.7 Representing Partial Orders by Set Containment
- 9.8 Path-Total Orders
- 9.9 Product Orders
- 9.10 Scheduling
- 9.11 Equivalence Relations
- “mcs” — 2011/5/9 — 20:49 — page v — #
- 9.12 Summary of Relational Properties Contentsv
- 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 Getting fromutovin a Graph
- 11.9 Connectivity
- 11.10 Odd Cycles and 2-Colorability
- 11.11 Forests & Trees
- 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 Another Characterization for Planar Graphs
- 12.7 Coloring Planar Graphs
- 12.8 Classifying Polyhedra
- 13 State Machines
- 13.1 The Alternating Bit Protocol
- 13.2 Reasoning AboutWhilePrograms
- “mcs” — 2011/5/9 — 20:49 — page vi — #
- 14 Sums and Asymptotics III Counting
- 14.1 The Value of an Annuity
- 14.2 Sums of Powers
- 14.3 Approximating Sums
- 14.4 Hanging Out Over the Edge
- 14.5 Products
- 14.6 Double Trouble
- 14.7 Asymptotic Notation
- 15 Cardinality Rules
- 15.1 Counting One Thing by Counting Another
- 15.2 Counting Sequences
- 15.3 The Generalized Product Rule
- 15.4 The Division Rule
- 15.5 Counting Subsets
- 15.6 Sequences with Repetitions
- 15.7 The Binomial Theorem
- 15.8 A Word about Words
- 15.9 Counting Practice: Poker Hands
- 15.10 Inclusion-Exclusion
- 15.11 Combinatorial Proofs
- 15.12 The Pigeonhole Principle
- 15.13 A Magic Trick
- 16 Events and Probability Spaces IV Probability
- 16.1 Let’s Make a Deal
- 16.2 The Four Step Method
- 16.3 Strange Dice
- 16.4 Set Theory and Probability
- 16.5 Conditional Probability
- 16.6 Independence
- 16.7 The Birthday Principle
- 17 Random Variables
- 17.1 Random Variable Examples
- “mcs” — 2011/5/9 — 20:49 — page vii — #
- 17.2 Independence Contentsvii
- 17.3 Distribution Functions
- 17.4 Great Expectations
- 17.5 Linearity of Expectation
- 18 Deviation from the Mean
- 18.1 Why the Mean?
- 18.2 Markov’s Theorem
- 18.3 Chebyshev’s Theorem
- 18.4 Properties of Variance
- 18.5 Estimation by Random Sampling
- 18.6 Confidence versus Probability
- 18.7 Sums of Random Variables
- 18.8 Really Great Expectations
- 19 Random Processes
- 19.1 Gamblers’ Ruin
- 19.2 Random Walks on Graphs
- Index
- “mcs” — 2011/5/9 — 20:49 — page viii — #
frankie
(Frankie)
#1