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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- discrete mathematics for computer science uh
- mathematics for computer science self application mit 6 042j 18 062j
- mathematics for computer science iit guwahati
- 6 00 introduction to computer science and mit opencourseware
- mathematics for computer science mit opencourseware
- s b and requirements checklist mit
- computer science mathematics columbia university
- mathematics for computer science eric lehman and tom leighton 2004
- mathematics for computer science bu
- discrete mathematics for computer science duke university
Related searches
- ideas for computer science project
- computer science projects for students
- computer science project topics and materials
- biology and computer science careers
- project topics for computer science students
- computer science for beginners pdf
- mathematics for computer science pdf
- difference between computer science and it
- salaries for computer science major
- physics and computer science jobs
- computer science questions and answers
- computer science projects for science fair