Mathematics for Computer Science - BU

[Pages:869]"mcs" -- 2013/8/17 -- 14:41 -- page i -- #1

Mathematics for Computer Science

revised Saturday 17th August, 2013, 14:41

Eric Lehman

Google Inc.

F Thomson Leighton

Department of Mathematics and the Computer Science and AI Laboratory,

Massachussetts Institute of Technology; Akamai Technologies

Albert R Meyer

Department of Electrical Engineering and Computer Science and the Computer Science and AI Laboratory, Massachussetts Institute of Technology

Creative Commons

2013, Eric Lehman, F Tom Leighton, Albert R Meyer .

"mcs" -- 2013/8/17 -- 14:41 -- page ii -- #2

"mcs" -- 2013/8/17 -- 14:41 -- page iii -- #3

Contents

I Proofs

Introduction 3

0.1 References 4

1 What is a Proof? 5

1.1 Propositions 5 1.2 Predicates 8 1.3 The Axiomatic Method 8 1.4 Our Axioms 9 1.5 Proving an Implication 11 1.6 Proving an "If and Only If" 13 1.7 Proof by Cases 15 1.8 Proof by Contradiction 16 1.9 Good Proofs in Practice 17 1.10 References 19

2 The Well Ordering Principle 25

2.1 Well Ordering Proofs 25 2.2 Template for Well Ordering Proofs 26 2.3 Factoring into Primes 28 2.4 Well Ordered Sets 29

3 Logical Formulas 39

3.1 Propositions from Propositions 40 3.2 Propositional Logic in Computer Programs 43 3.3 Equivalence and Validity 46 3.4 The Algebra of Propositions 48 3.5 The SAT Problem 53 3.6 Predicate Formulas 54 3.7 References 59

4 Mathematical Data Types 77

4.1 Sets 77 4.2 Sequences 81 4.3 Functions 81 4.4 Binary Relations 84 4.5 Finite Cardinality 88

"mcs" -- 2013/8/17 -- 14:41 -- page iv -- #4

iv

Contents

5 Induction 105

5.1 Ordinary Induction 105 5.2 Strong Induction 114 5.3 Strong Induction vs. Induction vs. Well Ordering 119 5.4 State Machines 120

6 Recursive Data Types 159

6.1 Recursive Definitions and Structural Induction 159 6.2 Strings of Matched Brackets 163 6.3 Recursive Functions on Nonnegative Integers 166 6.4 Arithmetic Expressions 169 6.5 Induction in Computer Science 174

7 Infinite Sets 191

7.1 Infinite Cardinality 192 7.2 The Halting Problem 199 7.3 The Logic of Sets 202 7.4 Does All This Really Work? 206

II Structures

Introduction 221

8 Number Theory 223

8.1 Divisibility 223 8.2 The Greatest Common Divisor 228 8.3 Prime Mysteries 234 8.4 The Fundamental Theorem of Arithmetic 237 8.5 Alan Turing 239 8.6 Modular Arithmetic 243 8.7 Remainder Arithmetic 245 8.8 Turing's Code (Version 2.0) 248 8.9 Multiplicative Inverses and Cancelling 250 8.10 Euler's Theorem 254 8.11 RSA Public Key Encryption 259 8.12 What has SAT got to do with it? 261 8.13 References 262

9 Directed graphs & Partial Orders 293

9.1 Vertex Degrees 295 9.2 Walks and Paths 296

"mcs" -- 2013/8/17 -- 14:41 -- page v -- #5

v

Contents

9.3 Adjacency Matrices 299 9.4 Walk Relations 301 9.5 Directed Acyclic Graphs & Scheduling 303 9.6 Partial Orders 310 9.7 Representing Partial Orders by Set Containment 313 9.8 Linear Orders 315 9.9 Product Orders 315 9.10 Equivalence Relations 316 9.11 Summary of Relational Properties 318

10 Communication Networks 345

10.1 Complete Binary Tree 345 10.2 Routing Problems 345 10.3 Network Diameter 346 10.4 Switch Count 347 10.5 Network Latency 348 10.6 Congestion 348 10.7 2-D Array 349 10.8 Butterfly 351 10.9 Benes Network 353

11 Simple Graphs 365

11.1 Vertex Adjacency and Degrees 365 11.2 Sexual Demographics in America 367 11.3 Some Common Graphs 369 11.4 Isomorphism 371 11.5 Bipartite Graphs & Matchings 373 11.6 The Stable Marriage Problem 378 11.7 Coloring 385 11.8 Simple Walks 389 11.9 Connectivity 391 11.10 Odd Cycles and 2-Colorability 394 11.11 Forests & Trees 396 11.12 References 405

12 Planar Graphs 435

12.1 Drawing Graphs in the Plane 435 12.2 Definitions of Planar Graphs 435 12.3 Euler's Formula 446 12.4 Bounding the Number of Edges in a Planar Graph 447 12.5 Returning to K5 and K3;3 448

"mcs" -- 2013/8/17 -- 14:41 -- page vi -- #6

vi

Contents

12.6 Coloring Planar Graphs 449 12.7 Classifying Polyhedra 451 12.8 Another Characterization for Planar Graphs 454

III Counting

Introduction 463

12.9 References 464

13 Sums and Asymptotics 465

13.1 The Value of an Annuity 466 13.2 Sums of Powers 472 13.3 Approximating Sums 474 13.4 Hanging Out Over the Edge 478 13.5 Products 485 13.6 Double Trouble 487 13.7 Asymptotic Notation 490

14 Cardinality Rules 509

14.1 Counting One Thing by Counting Another 509 14.2 Counting Sequences 510 14.3 The Generalized Product Rule 513 14.4 The Division Rule 517 14.5 Counting Subsets 520 14.6 Sequences with Repetitions 522 14.7 Counting Practice: Poker Hands 525 14.8 The Pigeonhole Principle 530 14.9 Inclusion-Exclusion 539 14.10 Combinatorial Proofs 545 14.11 References 549

15 Generating Functions 581

15.1 Infinite Series 581 15.2 Counting with Generating Functions 583 15.3 Partial Fractions 589 15.4 Solving Linear Recurrences 592 15.5 Formal Power Series 597 15.6 References 600

"mcs" -- 2013/8/17 -- 14:41 -- page vii -- #7

vii

Contents

IV Probability

Introduction 617

16 Events and Probability Spaces 619

16.1 Let's Make a Deal 619 16.2 The Four Step Method 620 16.3 Strange Dice 629 16.4 The Birthday Principle 637 16.5 Set Theory and Probability 639 16.6 References 643

17 Conditional Probability 651

17.1 Monty Hall Confusion 651 17.2 Definition and Notation 652 17.3 The Four-Step Method for Conditional Probability 654 17.4 Why Tree Diagrams Work 656 17.5 The Law of Total Probability 663 17.6 Simpson's Paradox 665 17.7 Independence 667 17.8 Mutual Independence 668

18 Random Variables 691

18.1 Random Variable Examples 691 18.2 Independence 693 18.3 Distribution Functions 694 18.4 Great Expectations 702 18.5 Linearity of Expectation 714

19 Deviation from the Mean 739

19.1 Markov's Theorem 739 19.2 Chebyshev's Theorem 742 19.3 Properties of Variance 746 19.4 Estimation by Random Sampling 750 19.5 Confidence versus Probability 756 19.6 Sums of Random Variables 757 19.7 Really Great Expectations 766

20 Random Walks 789

20.1 Gambler's Ruin 789 20.2 Random Walks on Graphs 799

"mcs" -- 2013/8/17 -- 14:41 -- page viii -- #8

viii

Contents

V Recurrences

Introduction 815

21 Recurrences 817

21.1 The Towers of Hanoi 817 21.2 Merge Sort 820 21.3 Linear Recurrences 824 21.4 Divide-and-Conquer Recurrences 831 21.5 A Feel for Recurrences 838

Bibliography 845 Glossary of Symbols 849 Index 852

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

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

Google Online Preview   Download