mathematicsforcomputerscience

mathematics for computer science - MIT open courseware.pdfmcs”-2012/l0/17-20:29— page lll-#3ContentsProofsIntroduction 31 What is a Proof? 51 Propositions 51.2 Predicates 81. 3 The Axiomatic Method 81. 4 Our axioms 91.5 Proving an Implication 1116 Proving an‘ If and Only If”131.7 Proof by cases 151. 8 Proof by Contradiction 161. 9 Good Proofs in Practice 171.10 References 192 The Well Ordering Principle 252.1 Well Ordering proofs 252.2 Template for Well Ordering Proofs 262. 3 Factoring into primes 282.4 Well Ordered sets 293 Logical Formulas 373.1 Propositions from Propositions 383.2 Propositional Logic in Computer Programs 413.3 Equivalence and validity 443.4 The Algebra of Propositions 463.5 The Sat Problem 513.6 Predicate Formulas 52Mathematical Data Types 734.1 Sets 734.2 Sequences 774.3 Functions 774.4 Binary Relations 804.5 Finite cardinality 845 nduction 995.1 Ordinary Induction 992012/10/17-20:29— page Iv-#Contents5.2 Strong Induction 1085.3 Strong Induction vs Induction vs. Well Ordering 1135.4 State machi1146 Recursive data Types 7576.1 Recursive Definitions and Structural Induction 1516.2 Strings of matched Brackets 1556.3 Recursive Functions on Nonnegative Integers 1586.4 Arithmetic Expressions 1616.5 Induction in Computer Science 1667 Infinite sets 1797. 1 Infinite Cardinality 1807.2 The halting Problem 1847.3 The Logic of Sets 1887.4 Does all This really work? 191I StructuresIntroduction 2058 Number Theory 2078.1 Divisibility 2078.2 The Greatest Common divisor 2128.3 Prime Mysteries 2188. 4 The fundamental theorem of arithmetic 2218.5 Alan Turing 2238.6 Modular arithmetic 2278.7 Remainder arithmetic 2298.8 Turings Code (version 2.0) 2328.9 Multiplicative Inverses and Cancelling 2348.10 Euler,s Theorem 2388.11 RSA Public Key Encryption 2458.12 What has sat got to do with it? 2488.13 References 2489 Directed graphs Partial Orders 2759.1 Digraphs vertex Degrees 2779.2 Adjacency Matrices 2819.3 Walk Relations 2849.4 Directed Acyclic graphs partial Orders 285s-2012/10/17—20:29page v#5Contents9.5 Weak Partial Orders 2889.6 Representing Partial Orders by Set Coent 2909.7 Path-Total Orders 2919.8 Product Orders 2929.9 Scheduling 2939.10 Equivalence Relations 2999. 11 Summary of Relational properties 30110 Communication Networks 32710.1 Complete binary tree 32710.2 Routing problems 32710.3 Network Diameter 32810.4 Switch Count 32910.5 Network Latency 33010.6 Congestion 33010.72 D Array33110.8 Butterfly 33310.9 Benes network 33511 Simple graphs 34711. 1 Vertex Adjacency and Degrees 34711.2 Sexual Demographics in America 34911.3 Some Common Graphs 35111.4 Isomorphism 35311.5 Bipartite Graphs Matchings 3511.6 The Stable Marriage Problem 36011.7 Coloring 36611. 8 Simple Walks 37111.9 Connectivity 37311.10 Odd Cycles and 2-Colorability 37611.11 Forests t37811.12 References 38612 Planar Graphs 41512.1 Drawing Graphs in the Plane 41512.2 Definitions of Planar Graplhs41512 3 Euler,s Formula 42612.4 Bounding the number of edges in a planar graph 42712.5 Returning to Ks and K3.3 42812.6 Coloring Planar Graphs 42912.7 Classifying Polyhedra 431mcs”-2012/l0/17-2029- page vI-#6ntents12.8 Another Characterization for Planar Graphs 434Il CountingIntroduction 44313 Sums and Asymptotics 44513. 1 The value of an annuity 44613.2 Sums of powers 45213.3 Approximating Sums 45413. 4 Hanging out over the edge 45813.5 Products 46.513.6 Double Trouble 46713.7 Asymptotic Notation 47014 Cardinality rules 48914.1 Counting One Thing by Counting Another 48914.2 Counting sequences 49014 3 The Generalized Product rule 49314. 4 The Division rule 49714.5 Counting Subsets 50014.6 Sequences with Repetitions 50214.7 Counting practice: Poker hands 50514.8 The Pigeonhole principle 51014.9 Inclusion-Exclusion 52014.10 Combinatorial Proofs 52614.11 References 53015 Generating Functions 56/15.1 Infinite s56l15.2 Counting with Generating Functions 56215.3 Partial fractions 56815.4 Solving Linear recurrences 57115.5 Formal Power Series 57615.6 References 580Ⅳ y ProbabilityIntroduction 59516 Events and probability spaces 597mcs2012/10/1720:29page Vll—#7ntents16.1 Lct's Makc a Deal 59716.2 The Four Step Method 59816.3 Strange Dice 60716.4 Set Theory and Probability 61517 Conditional Probability 62717.1 Definition and Notation 62817.2 Why Tree Diagrams Work 63017.3 A Posteriori Probabilities 63317. 4 The Law of Total probability 63517.5 Independence 63917.6 Mutual Independence 64017.7 The Birthday Principlle64518 Random variables 66518.1 Random Variable Examples 66518.2 Independence 66718.3 Distribution Functions 66818.4 Great Expectations 67618.5 Linearity of Expectation 68819 Deviation from the mean 7319.1 Why the Mean? 71319.2 Markov,s Theorem 71419.3 Chebyshevs Theorem 71619.4 Properties of Variance 72019.5 Estimation by Random Sampling 72519.6 Confidence versus Probability 73019.7 Sums of Random Variables 73119.8 Really great Expectations 74120 Random walks 76.320.1 Gambler,s Ruin 76320.2 Random Walks on Graphs 773V RecurrencesIntroduction 78921 Recurrences 79121.1 The Towers of hanoi 79121.2 Merge Sort 794mcs2012/10/1720:29page vi—#8VUContents21.3 Lincar Recurrences 79821.4 Divide-and-Conquer recurrences 80521.5 A Feel for Recurrences 812Bibliography 817Glossary of Symbols 821Index 824s-2012/10/17-20:29— page I-#9I Proofsmcs”-2012/10/17-20:29—page2—#l0