Mathematics for Computer Science Eric Lehman and Tom Leighton 2004

Mathematics for Computer Science

Eric Lehman and Tom Leighton

2004

2

Contents

1

2

3

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

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

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

4

CONTENTS

Number Theory I

4.1

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

4.2

Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.3

5

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

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

Number Theory II

5.1

6

45

61

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

Graph Theory

6.1

73

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

7

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

Graph Theory II

7.1

7.2

7.3

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

7.1.1

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

7.1.2

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

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

7.2.1

Euler¡¯s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7.2.2

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

Hall¡¯s Marriage Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7.3.1

8

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

Communication Networks

8.1

89

99

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

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

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

Google Online Preview   Download