Mathematics For Computing Science

“mcs-ftl” — 2010/9/8 — 0:40 — page i — #1

Mathematics for Computer Science
revised Wednesday 8th September, 2010, 00:40

Eric Lehman
Google Inc.

F Thomson Leighton
Department of Mathematics and CSAIL, MIT
Akamai Technologies

Albert R Meyer
Massachusets Institute of Technology

Copyright © 2010, Eric Lehman, F Tom Leighton, Albert R Meyer . All rights reserved.

“mcs-ftl” —2010/9/8 — 0:40 — page ii — #2

“mcs-ftl” — 2010/9/8 — 0:40 — page iii — #3

Contents
I

Proofs
1

Propositions 5
1.1
1.2
1.3
1.4
1.5

2

The Axiomatic Method
23
Proof by Cases
26
Proving an Implication
27
Proving an “If and Only If”
30
Proof by Contradiction
32
Proofs about Sets
33
Good Proofs in Practice
40

Induction 43
3.1
3.2
3.3
3.4
3.5

4

10Patterns of Proof 23
2.1
2.2
2.3
2.4
2.5
2.6
2.7

3

Compound Propositions
6
Propositional Logic in Computer Programs
Predicates and Quantifiers
11
Validity
19
Satisfiability
21

The Well Ordering Principle
Ordinary Induction
46
Invariants
56
Strong Induction
64
Structural Induction
69

43

Number Theory 81
4.1
4.2
4.3
4.4
4.5
4.6
4.7
4.8

Divisibility
81The Greatest Common Divisor
87
The Fundamental Theorem of Arithmetic
94
Alan Turing
96
Modular Arithmetic 100
Arithmetic with a Prime Modulus 103
Arithmetic with an Arbitrary Modulus 108
The RSA Algorithm 113

“mcs-ftl” — 2010/9/8 — 0:40 — page iv — #4

iv

Contents

II Structures
5

Graph Theory 121
5.1
5.2
5.3
5.4
5.5
5.6
5.7
5.8

6

Directed Graphs 189
6.1
6.26.3

7

Definitions 189
Tournament Graphs 192
Communication Networks

196

Relations and Partial Orders 213
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
7.9

8

Definitions 121
Matching Problems 128
Coloring 143
Getting from A to B in a Graph 147
Connectivity 151
Around and Around We Go 156
Trees 162
Planar Graphs 170

Binary Relations 213
Relations and Cardinality 217
Relationson One Set 220
Equivalence Relations 222
Partial Orders 225
Posets and DAGs 226
Topological Sort 229
Parallel Task Scheduling 232
Dilworth’s Lemma 235

State Machines 237

III Counting
9

Sums and Asymptotics 243
9.1
9.2
9.3
9.4
9.5
9.6

The Value of an Annuity 244
Power Sums 250
Approximating Sums 252
Hanging Out Over the Edge 257
Double Trouble 269
Products 272“mcs-ftl” — 2010/9/8 — 0:40 — page v — #5

v

Contents

9.7

Asymptotic Notation

275

10 Recurrences 283
10.1
10.2
10.3
10.4
10.5

The Towers of Hanoi 284
Merge Sort 291
Linear Recurrences 294
Divide-and-Conquer Recurrences
A Feel for Recurrences 309

302

11 Cardinality Rules 313
11.1 Counting One Thing by Counting Another
11.2 Counting Sequences 314
11.3 The GeneralizedProduct Rule 317
11.4 The Division Rule 321
11.5 Counting Subsets 324
11.6 Sequences with Repetitions 326
11.7 Counting Practice: Poker Hands 329
11.8 Inclusion-Exclusion 334
11.9 Combinatorial Proofs 339
11.10 The Pigeonhole Principle 342
11.11 A Magic Trick 346

12 Generating Functions 355
12.1
12.2
12.3
12.4
12.5
12.6

Definitions and Examples 355
Operations on GeneratingFunctions 356
Evaluating Sums 361
Extracting Coefficients 363
Solving Linear Recurrences 370
Counting with Generating Functions 374

13 Infinite Sets 379
13.1
13.2
13.3
13.4

Injections, Surjections, and Bijections
Countable Sets 381
Power Sets Are Strictly Bigger 384
Infinities in Computer Science 386

IV Probability
14 Events and Probability Spaces 391
14.1 Let’s Make a Deal 39114.2 The Four Step Method 392

379

313

“mcs-ftl” — 2010/9/8 — 0:40 — page vi — #6

vi

Contents

14.3 Strange Dice 402
14.4 Set Theory and Probability 411
14.5 Infinite Probability Spaces 413

15 Conditional Probability 417
15.1
15.2
15.3
15.4

Definition 417
Using the Four-Step Method to Determine Conditional Probability
A Posteriori Probabilities 424
Conditional...