Mathematics for Computer Science Eric Lehman and Tom ...

1 Mathematics for Computer ScienceEric Lehman and Tom Leighton20042 Contents1 What is a Proof? Propositions.. Axioms.. Logical Deductions.. Examples of Proofs.. A Tautology.. A Proof by Contradiction..222 Induction A Warmup Puzzle.. Induction.. Using Induction.. A Divisibility Theorem.. A Faulty Induction Proof.. Courtyard Tiling.. Another Faulty Proof..333 Induction Good Proofs and Bad Proofs.. A Puzzle.. Unstacking.. Strong Induction.. Analyzing the Game..4134 CONTENTS4 Number Theory A Theory of the Integers.. Divisibility.. Turing s Code (Version ).. The Division Algorithm.

2 Breaking Turing s Code.. Modular Arithmetic.. Congruence and Remainders.. Facts about rem and mod.. Turing s Code (Version ).. Cancellation Modulo a Prime.. Multiplicative Inverses.. Fermat s Theorem.. Finding Inverses with Fermat s Theorem.. Breaking Turing s Code Again..585 Number Theory Die Hard.. Death by Induction.. A General Theorem.. The Greatest Common Divisor.. Properties of the Greatest Common Divisor.. The Fundamental Theorem of Arithemtic.. Arithmetic with an Arbitrary Modulus.. Relative Primality and Phi.. Generalizing to an Arbitrary Modulus.. Euler s Theorem.

3 716 Graph Introduction.. Definitions.. Sex in America.. Graph Variations.. Applications of Graphs.. Some Common Graphs.. Isomorphism.. Connectivity.. A Simple Connectivity Theorem.. Distance and Diameter.. Walks.. Adjacency Matrices.. Trees.. Spanning Trees.. Tree Variations..877 Graph Theory Coloring Graphs.. k-Coloring.. Bipartite Graphs.. Planar Graphs.. Euler s Formula.. Classifying Polyhedra.. Hall s Marriage Theorem.. A Formal Statement..978 Communication Complete Binary Tree.. Latency and Diameter.. Switch Size.. Switch Count.. Congestion.. 2-D Array.

4 Butterfly.. Bene s Network..1066 CONTENTS9 Relations on One Set.. Relations and Directed Graphs.. Properties of Relations.. Equivalence Relations.. Partitions.. Partial Orders.. Directed Acyclic Graphs.. Partial Orders and Total Orders..11610 Sums, Approximations, and The Value of an Annuity.. The Future Value of Money.. A Geometric Sum.. Return of the Annuity Problem.. Infinite Sums.. Variants of Geometric Sums.. Sums of Powers.. Approximating Sums.. Integration Bounds.. Taylor s Theorem.. Back to the Sum.. Another Integration Example..13111 Sums, Approximations, and Asymptotics Block Stacking.

5 Harmonic Numbers.. Products.. Asymptotic Notation..138 CONTENTS712 Recurrences The Towers of Hanoi.. Finding a Recurrence.. A Lower Bound for Towers of Hanoi.. Guess-and-Verify.. The Plug-and-Chug Method.. Merge Sort.. The Algorithm.. Finding a Recurrence.. Solving the Recurrence.. More Recurrences.. A Speedy Algorithm.. A Verification Problem.. A False Proof.. Altering the Number of Subproblems.. The Akra-Bazzi Method.. Solving Divide and Conquer Recurrences..15613 Recurrences Asymptotic Notation and Induction.. Linear Recurrences.. Graduate Student Job Prospects.. Finding a Recurrence.

6 Solving the Recurrence.. Job Prospects.. General Linear Recurrences.. An Example.. Inhomogeneous Recurrences.. An Example.. How to Guess a Particular Solution..1698 CONTENTS14 Counting Counting One Thing by Counting Another.. Functions.. Bijections.. The Bijection Rule.. Sequences.. Two Basic Counting Rules.. The Sum Rule.. The Product Rule.. Putting Rules Together.. More Functions: Injections and Surjections.. The Pigeonhole Principle..18215 Counting The Generalized Product Rule.. Defective Dollars.. A Chess Problem.. Permutations.. The Division Rule.. Another Chess Problem.. Knights of the Round Table.

7 Inclusion-Exclusion.. Union of Two Sets.. Union of Three Sets.. Union ofnSets.. The Grand Scheme for Counting..19716 Counting The Bookkeeper Rule.. 20-Mile Walks.. Bit Sequences.. Subsets of ann-element Set.. An Alternative Derivation.. Word of Caution.. Binomial Theorem.. Poker Hands.. Hands with a Four-of-a-Kind.. Hands with a Full House.. Hands with Two Pairs.. Hands with Every Suit.. Magic Trick.. The Secret.. The Real Secret.. Same Trick with Four Cards?.. Combinatorial Proof.. Boxing.. Combinatorial Proof..21417 Generating Generating Functions.. Operations on Generating Functions.

8 Scaling.. Addition.. Right Shifting.. Differentiation.. The Fibonacci Sequence.. Finding a Generating Function.. Finding a Closed Form.. Counting with Generating Functions.. Choosing Distinct Items from a Set.. Building Generating Functions that Count.. Choosing Items with Repetition.. An Impossible Counting Problem..22910 CONTENTS18 Introduction to Monty Hall.. The Four-Step Method.. Clarifying the Problem.. Step 1: Find the Sample Space.. Step 2: Define Events of Interest.. Step 3: Determine Outcome Probabilities.. Step 4: Compute Event Probabilities.. An Alternative Interpretation of the Monty Hall Problem.

9 Strange Dice.. Analysis of Strange Dice..24119 Conditional The Halting Problem.. Solution to the Halting Problem.. Why Tree Diagrams Work.. PosterioriProbabilities.. A Coin Problem.. A Variant of the Two Coins Problem.. Medical Testing.. Conditional Probability Pitfalls.. Carnival Dice.. Other Identities.. Discrimination Lawsuit.. On-Time Airlines..26020 Independent Events.. Examples.. Working with Independence.. Some Intuition.. An Experiment with Two Coins.. A Variation of the Two-Coin Experiment.. Mutual Independence.. DNA Testing.. Pairwise Independence.. The Birthday Paradox.. The Four-Step Method.

10 An Alternative Approach.. An Upper Bound.. A Lower Bound.. The Birthday Principle..27521 Random Random Variables.. Indicator Random Variables.. Random Variables and Events.. Conditional Probability.. Independence.. An Example with Dice.. Probability Distributions.. Bernoulli Distribution.. Uniform Distribution.. The Numbers Game.. Binomial Distribution.. Approximating the Cumulative Binomial Distribution Function.. Philosophy of Polling..29122 Expected Value Betting on Coins.. Equivalent Definitions of Expectation.. Mean Time to Failure.. Making a Baby Girl.. An Expectation Paradox.. Linearity of Expectation.