Mathematics for Computer Science

Contents
I Proofs
Introduction 3
0.1 References 4
1 What is a Proof? 5
1.1 Propositions 5
1.2 Predicates 8
1.3 The Axiomatic Method 8
1.4 Our Axioms 9
1.5 Proving an Implication 11
1.6 Proving an “If and Only If” 13
1.7 Proof by Cases 15
1.8 Proof by Contradiction 16
1.9 Good Proofs in Practice 17
1.10 References 19
2 The Well Ordering Principle 29
2.1 Well Ordering Proofs 29
2.2 Template for Well Ordering Proofs 30
2.3 Factoring into Primes 32
2.4 Well Ordered Sets 33
3 Logical Formulas 45
3.1 Propositions from Propositions 46
3.2 Propositional Logic in Computer Programs 50
3.3 Equivalence and Validity 52
3.4 The Algebra of Propositions 55
3.5 The SAT Problem 60
3.6 Predicate Formulas 61
3.7 References 66
4 Mathematical Data Types 91
4.1 Sets 91
4.2 Sequences 96
4.3 Functions 97
4.4 Binary Relations 99
4.5 Finite Cardinality 103
5 Induction 123
5.1 Ordinary Induction 123
5.2 Strong Induction 132
5.3 Strong Induction vs. Induction vs. Well Ordering 139
6 State Machines 159
6.1 States and Transitions 159
6.2 The Invariant Principle 160
6.3 Partial Correctness & Termination 168
6.4 The Stable Marriage Problem 173
7 Recursive Data Types 203
7.1 Recursive Definitions and Structural Induction 203
7.2 Strings of Matched Brackets 207
7.3 Recursive Functions on Nonnegative Integers 211
7.4 Arithmetic Expressions 213
7.5 Induction in Computer Science 218
8 Infinite Sets 245
8.1 Infinite Cardinality 246
8.2 The Halting Problem 255
8.3 The Logic of Sets 259
8.4 Does All This Really Work? 262
II Structures
Introduction 287
9 Number Theory 289
9.1 Divisibility 289
9.2 The Greatest Common Divisor 294
9.3 Prime Mysteries 301
9.4 The Fundamental Theorem of Arithmetic 303
9.5 Alan Turing 306
9.6 Modular Arithmetic 310
9.7 Remainder Arithmetic 312
9.8 Turing’s Code (Version 2.0) 315
9.9 Multiplicative Inverses and Cancelling 317
9.10 Euler’s Theorem 321
9.11 RSA Public Key Encryption 326
9.12 What has SAT got to do with it? 328
9.13 References 329
10 Directed graphs & Partial Orders 367
10.1 Vertex Degrees 369
10.2 Walks and Paths 370
10.3 Adjacency Matrices 373
10.4 Walk Relations 376
10.5 Directed Acyclic Graphs & Scheduling 377
10.6 Partial Orders 385
10.7 Representing Partial Orders by Set Containment 389
10.8 Linear Orders 390
10.9 Product Orders 390
10.10 Equivalence Relations 391
10.11 Summary of Relational Properties 393
11 Communication Networks 425
11.1 Routing 425
11.2 Routing Measures 426
11.3 Network Designs 429
12 Simple Graphs 445
12.1 Vertex Adjacency and Degrees 445
12.2 Sexual Demographics in America 447
12.3 Some Common Graphs 449
12.4 Isomorphism 451
12.5 Bipartite Graphs & Matchings 453
12.6 Coloring 458
12.7 Simple Walks 463
12.8 Connectivity 465
12.9 Forests & Trees 470
12.10 References 478
13 Planar Graphs 517
13.1 Drawing Graphs in the Plane 517
13.2 Definitions of Planar Graphs 517
13.3 Euler’s Formula 528
13.4 Bounding the Number of Edges in a Planar Graph 529
13.5 Returning to K5 and K3;3 530
13.6 Coloring Planar Graphs 531
13.7 Classifying Polyhedra 533
13.8 Another Characterization for Planar Graphs 536
III Counting
Introduction 545
14 Sums and Asymptotics 547
14.1 The Value of an Annuity 548
14.2 Sums of Powers 554
14.3 Approximating Sums 556
14.4 Hanging Out Over the Edge 560
14.5 Products 566
14.6 Double Trouble 569
14.7 Asymptotic Notation 572
15 Cardinality Rules 597
15.1 Counting One Thing by Counting Another 597
15.2 Counting Sequences 598
15.3 The Generalized Product Rule 601
15.4 The Division Rule 605
15.5 Counting Subsets 608
15.6 Sequences with Repetitions 610
15.7 Counting Practice: Poker Hands 613
15.8 The Pigeonhole Principle 618
15.9 Inclusion-Exclusion 627
15.10 Combinatorial Proofs 633
15.11 References 637
16 Generating Functions 675
16.1 Infinite Series 675
16.2 Counting with Generating Functions 677
16.3 Partial Fractions 683
16.4 Solving Linear Recurrences 686
16.5 Formal Power Series 691
16.6 References 694
IV Probability
Introduction 713
17 Events and Probability Spaces 715
17.1 Let’s Make a Deal 715
17.2 The Four Step Method 716
17.3 Strange Dice 725
17.4 The Birthday Principle 732
17.5 Set Theory and Probability 734
17.6 References 738
18 Conditional Probability 747
18.1 Monty Hall Confusion 747
18.2 Definition and Notation 748
18.3 The Four-Step Method for Conditional Probability 750
18.4 Why Tree Diagrams Work 752
18.5 The Law of Total Probability 760
18.6 Simpson’s Paradox 762
18.7 Independence 764
18.8 Mutual Independence 766
18.9 Probability versus Confidence 770
19 Random Variables 799
19.1 Random Variable Examples 799
19.2 Independence 801
19.3 Distribution Functions 802
19.4 Great Expectations 811
19.5 Linearity of Expectation 822
20 Deviation from the Mean 853
20.1 Markov’s Theorem 853
20.2 Chebyshev’s Theorem 856
20.3 Properties of Variance 860
20.4 Estimation by Random Sampling 866
20.5 Confidence in an Estimation 869
20.6 Sums of Random Variables 871
20.7 Really Great Expectations 880
21 Random Walks 905
21.1 Gambler’s Ruin 905
21.2 Random Walks on Graphs 915
V Recurrences
Introduction 933
22 Recurrences 935
22.1 The Towers of Hanoi 935
22.2 Merge Sort 938
22.3 Linear Recurrences 942
22.4 Divide-and-Conquer Recurrences 949
22.5 A Feel for Recurrences 956
Bibliography 963
Glossary of Symbols 967
Index 971