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.
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
- project topics for computer science students
- computer science for beginners pdf
- is computer science for me
- is computer science right for me
- study computer science for free
- mathematics for computer science pdf
- salaries for computer science major
- computer science articles for students
- computer science basics for beginners
- computer science for high schoolers