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 1.1 1.2 1.3 1.4 1.5

2

23

43

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

Number Theory 4.1 4.2 4.3 4.4 4.5 4.6 4.7 4.8

10

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 3.1 3.2 3.3 3.4 3.5

4

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

Patterns of Proof 2.1 2.2 2.3 2.4 2.5 2.6 2.7

3

5

43

81

Divisibility 81 The 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 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8

6

7

189

Definitions 189 Tournament Graphs 192 Communication Networks

Relations and Partial Orders 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

Directed Graphs 6.1 6.2 6.3

121

196

213

Binary Relations 213 Relations and Cardinality 217 Relations on 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 9.1 9.2 9.3 9.4 9.5 9.6

243

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

10 Recurrences 10.1 10.2 10.3 10.4 10.5

275

283

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

11 Cardinality Rules

302

313

11.1 Counting One Thing by Counting Another 11.2 Counting Sequences 314 11.3 The Generalized Product 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 12.1 12.2 12.3 12.4 12.5 12.6

355

Definitions and Examples 355 Operations on Generating Functions 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 1