Mathematics for Computer Science Eric Lehman and Tom ...

[Pages:339]Mathematics for Computer Science Eric Lehman and Tom Leighton 2004

2

Contents

1 What is a Proof?

15

1.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3 Logical Deductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.4 Examples of Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.4.1 A Tautology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.4.2 A Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 Induction I

23

2.1 A Warmup Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Using Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4 A Divisibility Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.5 A Faulty Induction Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.6 Courtyard Tiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.7 Another Faulty Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3 Induction II

35

3.1 Good Proofs and Bad Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 A Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.3 Unstacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.1 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.2 Analyzing the Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3

4

CONTENTS

4 Number Theory I

45

4.1 A Theory of the Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2.1 Turing's Code (Version 1.0) . . . . . . . . . . . . . . . . . . . . . . . . 47

4.2.2 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.2.3 Breaking Turing's Code . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3.1 Congruence and Remainders . . . . . . . . . . . . . . . . . . . . . . . 51

4.3.2 Facts about rem and mod . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.3 Turing's Code (Version 2.0) . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.4 Cancellation Modulo a Prime . . . . . . . . . . . . . . . . . . . . . . . 55

4.3.5 Multiplicative Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.3.6 Fermat's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.3.7 Finding Inverses with Fermat's Theorem . . . . . . . . . . . . . . . . 58

4.3.8 Breaking Turing's Code-- Again . . . . . . . . . . . . . . . . . . . . . 58

5 Number Theory II

61

5.1 Die Hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.1.1 Death by Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.1.2 A General Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.1.3 The Greatest Common Divisor . . . . . . . . . . . . . . . . . . . . . . 64

5.1.4 Properties of the Greatest Common Divisor . . . . . . . . . . . . . . . 65

5.2 The Fundamental Theorem of Arithemtic . . . . . . . . . . . . . . . . . . . . 67

5.3 Arithmetic with an Arbitrary Modulus . . . . . . . . . . . . . . . . . . . . . . 68

5.3.1 Relative Primality and Phi . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.3.2 Generalizing to an Arbitrary Modulus . . . . . . . . . . . . . . . . . . 70

5.3.3 Euler's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6 Graph Theory

73

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.1.2 Sex in America . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

CONTENTS

5

6.1.3 Graph Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 6.1.4 Applications of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.1.5 Some Common Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 77 6.1.6 Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 6.2 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 6.2.1 A Simple Connectivity Theorem . . . . . . . . . . . . . . . . . . . . . 80 6.2.2 Distance and Diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 6.2.3 Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.3 Adjacency Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 6.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 6.4.1 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 6.4.2 Tree Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

7 Graph Theory II

89

7.1 Coloring Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.1.1 k-Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.1.2 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.2 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

7.2.1 Euler's Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7.2.2 Classifying Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

7.3 Hall's Marriage Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7.3.1 A Formal Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

8 Communication Networks

99

8.1 Complete Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

8.1.1 Latency and Diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

8.1.2 Switch Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

8.1.3 Switch Count . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

8.1.4 Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

8.2 2-D Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8.3 Butterfly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

8.4 Benes Network . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

6

CONTENTS

9 Relations

111

9.0.1 Relations on One Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

9.0.2 Relations and Directed Graphs . . . . . . . . . . . . . . . . . . . . . . 112

9.1 Properties of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

9.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

9.2.1 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

9.3 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

9.3.1 Directed Acyclic Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 116

9.3.2 Partial Orders and Total Orders . . . . . . . . . . . . . . . . . . . . . . 116

10 Sums, Approximations, and Asymptotics

119

10.1 The Value of an Annuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

10.1.1 The Future Value of Money . . . . . . . . . . . . . . . . . . . . . . . . 119

10.1.2 A Geometric Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

10.1.3 Return of the Annuity Problem . . . . . . . . . . . . . . . . . . . . . . 121

10.1.4 Infinite Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

10.2 Variants of Geometric Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

10.3 Sums of Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

10.4 Approximating Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

10.4.1 Integration Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

10.4.2 Taylor's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

10.4.3 Back to the Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

10.4.4 Another Integration Example . . . . . . . . . . . . . . . . . . . . . . . 131

11 Sums, Approximations, and Asymptotics II

133

11.1 Block Stacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

11.1.1 Harmonic Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

11.2 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

11.3 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

CONTENTS

7

12 Recurrences I

143

12.1 The Towers of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

12.1.1 Finding a Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

12.1.2 A Lower Bound for Towers of Hanoi . . . . . . . . . . . . . . . . . . . 145

12.1.3 Guess-and-Verify . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

12.1.4 The Plug-and-Chug Method . . . . . . . . . . . . . . . . . . . . . . . 147

12.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

12.2.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

12.2.2 Finding a Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

12.2.3 Solving the Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

12.3 More Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

12.3.1 A Speedy Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

12.3.2 A Verification Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

12.3.3 A False Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

12.3.4 Altering the Number of Subproblems . . . . . . . . . . . . . . . . . . 155

12.4 The Akra-Bazzi Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

12.4.1 Solving Divide and Conquer Recurrences . . . . . . . . . . . . . . . . 156

13 Recurrences II

159

13.1 Asymptotic Notation and Induction . . . . . . . . . . . . . . . . . . . . . . . 159

13.2 Linear Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

13.2.1 Graduate Student Job Prospects . . . . . . . . . . . . . . . . . . . . . 160

13.2.2 Finding a Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

13.2.3 Solving the Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

13.2.4 Job Prospects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

13.3 General Linear Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

13.3.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

13.4 Inhomogeneous Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

13.4.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

13.4.2 How to Guess a Particular Solution . . . . . . . . . . . . . . . . . . . 169

8

CONTENTS

14 Counting I

173

14.1 Counting One Thing by Counting Another . . . . . . . . . . . . . . . . . . . 174

14.1.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

14.1.2 Bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

14.1.3 The Bijection Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

14.1.4 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

14.2 Two Basic Counting Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

14.2.1 The Sum Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

14.2.2 The Product Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

14.2.3 Putting Rules Together . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

14.3 More Functions: Injections and Surjections . . . . . . . . . . . . . . . . . . . 181

14.3.1 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . 182

15 Counting II

187

15.1 The Generalized Product Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

15.1.1 Defective Dollars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

15.1.2 A Chess Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

15.1.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

15.2 The Division Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

15.2.1 Another Chess Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 191

15.2.2 Knights of the Round Table . . . . . . . . . . . . . . . . . . . . . . . . 192

15.3 Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

15.3.1 Union of Two Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

15.3.2 Union of Three Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

15.3.3 Union of n Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

15.4 The Grand Scheme for Counting . . . . . . . . . . . . . . . . . . . . . . . . . 197

16 Counting III

201

16.1 The Bookkeeper Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

16.1.1 20-Mile Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

16.1.2 Bit Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

16.1.3 k-element Subsets of an n-element Set . . . . . . . . . . . . . . . . . . 202

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download