Mathematics for Computer Science

I Proofs 1 Propositions 1.1 Compound Propositions 1.2 Propositional Logic in Computer Programs 1.3 Predicates and Quantifiers 1.4 Validity 1.5 Satisfiability 2 Patterns of Proof 2.1 The Axiomatic Method 2.2 Proof by Cases 2.3 Proving an Implication 2.4 Proving an ``If and Only If'' 2.5 Proof by Contradiction 2.6 Proofs about Sets 2.7 Good Proofs in Practice 3 Induction 3.1 The Well Ordering Principle 3.2 Ordinary Induction 3.3 Invariants 3.4 Strong Induction 3.5 Structural Induction 4 Number Theory 4.1 Divisibility 4.2 The Greatest Common Divisor 4.3 The Fundamental Theorem of Arithmetic 4.4 Alan Turing 4.5 Modular Arithmetic 4.6 Arithmetic with a Prime Modulus 4.7 Arithmetic with an Arbitrary Modulus 4.8 The RSA Algorithm II Structures 5 Graph Theory 5.1 Definitions 5.2 Matching Problems 5.3 Coloring 5.4 Getting from A to B in a Graph 5.5 Connectivity 5.6 Around and Around We Go 5.7 Trees 5.8 Planar Graphs 6 Directed Graphs 6.1 Definitions 6.2 Tournament Graphs 6.3 Communication Networks 7 Relations and Partial Orders 7.1 Binary Relations 7.2 Relations and Cardinality 7.3 Relations on One Set 7.4 Equivalence Relations 7.5 Partial Orders 7.6 Posets and DAGs 7.7 Topological Sort 7.8 Parallel Task Scheduling 7.9 Dilworth's Lemma 8 State Machines III Counting 9 Sums and Asymptotics 9.1 The Value of an Annuity 9.2 Power Sums 9.3 Approximating Sums 9.4 Hanging Out Over the Edge 9.5 Double Trouble 9.6 Products 9.7 Asymptotic Notation 10 Recurrences 10.1 The Towers of Hanoi 10.2 Merge Sort 10.3 Linear Recurrences 10.4 Divide-and-Conquer Recurrences 10.5 A Feel for Recurrences 11 Cardinality Rules 11.1 Counting One Thing by Counting Another 11.2 Counting Sequences 11.3 The Generalized Product Rule 11.4 The Division Rule 11.5 Counting Subsets 11.6 Sequences with Repetitions 11.7 Counting Practice: Poker Hands 11.8 Inclusion-Exclusion 11.9 Combinatorial Proofs 11.10 The Pigeonhole Principle 11.11 A Magic Trick 12 Generating Functions 12.1 Definitions and Examples 12.2 Operations on Generating Functions 12.3 Evaluating Sums 12.4 Extracting Coefficients 12.5 Solving Linear Recurrences 12.6 Counting with Generating Functions 13 Infinite Sets 13.1 Injections, Surjections, and Bijections 13.2 Countable Sets 13.3 Power Sets Are Strictly Bigger 13.4 Infinities in Computer Science IV Probability 14 Events and Probability Spaces 14.1 Let's Make a Deal 14.2 The Four Step Method 14.3 Strange Dice 14.4 Set Theory and Probability 14.5 Infinite Probability Spaces 15 Conditional Probability 15.1 Definition 15.2 Using the Four-Step Method to Determine Conditional Probability 15.3 A Posteriori Probabilities 15.4 Conditional Identities 16 Independence 16.1 Definitions 16.2 Independence Is an Assumption 16.3 Mutual Independence 16.4 Pairwise Independence 16.5 The Birthday Paradox 17 Random Variables and Distributions 17.1 Definitions and Examples 17.2 Distribution Functions 17.3 Bernoulli Distributions 17.4 Uniform Distributions 17.5 Binomial Distributions 18 Expectation 18.1 Definitions and Examples 18.2 Expected Returns in Gambling Games 18.3 Expectations of Sums 18.4 Expectations of Products 18.5 Expectations of Quotients 19 Deviations 19.1 Variance 19.2 Markov's Theorem 19.3 Chebyshev's Theorem 19.4 Bounds for Sums of Random Variables 19.5 Mutually Independent Events 20 Random Walks 20.1 Unbiased Random Walks 20.2 Gambler's Ruin 20.3 Walking in Circles