Mathematics for Computer Science

This text explains how to use mathematical models and methods to analyze problems that arise in computer science.mcs”-20173/23-23:53age iii -#3ContentsI ProofsIntroduction 30.1 References 41 What is a Proof? 51.1 Propositions1.2 Predicates 81. 3 The axiomatic method 81. 4 Our axioms 91.5 Proving an Implication 111.6 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 292.1 Well Ordering Proofs 292. 2 Template for Well Ordering Proofs 302. 3 Factoring into Primes 322.4 Well orSets 333 Logical Formulas 473.1 Propositions from Propositions 483.2 Propositional logic in Computer Programs 523.3 Equivalence and Validity543.4 The Algebra of Propositions 573.5 The Sat Problem 623.6 Predicate Formulas 633.7 References 684 Mathematical Data Types 954.1 Sets 954.2 Seque4.3 Functions 1014.4 Binary relations 1034.5 Finite Cardinality 107mcs-2017/3/2323:53page—#4Contents5 Induction 1275.1 Ordinary Induction 1275.2 Strong Induction 1365.3 Strong induction vs. Induction vs Well ordering 1436 State Machines 1636.1 States and Transitions 1636.2 The Invariant Principle 1646.3 Partial Correctness Termination 1726.4 The Stable marriage Problem 1777 Recursive Data Types 2077. 1 Recursive Definitions and Structural Induction 2077.2 Strings of Matched Brackets 2117.3 Recursive Functions on Nonnegative Integers 2157.4 Arithmetic Expressions 2177.5 Games as a Recursive Data Type 2227.6 Induction in Computer Science 2268 Infinite Sets 2538.1 Infinite Cardinality 2548.2 The halting Problem 2638. 3 The Logic of Sets 2678.4 Does all this really work? 271I StructuresIntroduction 2959 Number Theory 2979.1 Divisibility 2979.2 The Greatest Common Divisor 3029.3 Prime mysteries 3099.4 The Fundamental Theorem of Arithmetic 3119.5 Alan Turing 3149.6 Modular arithmetic 31 89.7 Remainder arithmetic 3209. 8 Turings Code( version 2.0) 3239.9 Multiplicative Inverses and Cancelling 3259.10 Euler's Theorem 3299. 11 RSa Public Key encryption 334mcs2017/3/2323:53age v#5Contents9 12 What has sat got to do with it? 3369.13 References 33710 Directed graphs Partial Orders 3750.1 Vertex degrees 37710.2 Walks and paths 37810.3 Adjacency Matrices 3810.4 Walk relations 38410.5 Directed Acyclic Graphs scheduling 38.510.6 Partial Orders 39310.7 Representing Partial Orders by Set Containment 39710.8 Linear Orders 39810.9 Product Orders 39810.10 Equivalence relations 39910.11 Summary of relational Properties 40111 Communication networks 43311.1 Routing 43311.2 Routing measures 43411. 3 Network designs 43712 Simple graphs 45312. 1 Vertex Adjacency and Degrees 45312.2 Sexual demographics in America 45512.3 Some Common Graphs 45712.4 Isomorphism 45912.5 Bipartite graphs matchings 46112.6 Coloring 46612.7 Simple walks 47112.8 ConnectiⅤiv47312.9 Forests t47812.10 References 48613 Planar Graphs 52513. 1 Drawing graphs in the plane 52513.2 Definitions of Planar graphs 52513.3 Euler's Formula 53613.5 Returning to Ks and K3, 3 s t a Planar Graph 53713. 4 Bounding the number of edges i13.6 Coloring Planar Graphs 53913.7 Classifying Polyhedra 54113.8 Another Characterization for Planar graphs 544mcs”-2017/3/23-23:53- page vI-ContentsIll CountingIntroduction 55314 Sums and Asymptotics 55514.1 The Value of an annuity 55614.2 Sums of powers 56214.3 Approximating Sums 56414.4 Hanging out over the edge 568145 Products 57414.6 Double Trouble 57714.7 Asymptotic Notation 58015 Cardinality Rules 60515.1 Counting One Thing by Counting Another 60515.2 Counting Sequences 60615.3 The Generalized Product Rule 60915.4 The division rule 61315.5 Counting subsets 61615.6 Sequences with Repetitions 61815.7 Counting Practice: Poker hands 62115.8 The Pigeonhole Principle 62615.9 Inclusion-Exclusion 63515.10 Combinatorial Proofs 64115.11 References 64516 Generating Functions 68316.1 Infinite series 68316.2 Counting with Generating Functions 68516.3 Partial Fractions 69116.4 Solving Linear recurrences 69416.5 Formal Power Series 69916.6 References 702IV ProbabilityIntroduction 72117 Events and Probability spaces 72317.1 Let's make a Deal 723mcs”-20173/23-23:53- page vIl-#7Contents17.2 The Four Step Method 72417.3 Strange Dice 73317.4 The Birthday Principle 74017.5 Set Theory and Probability 74217.6 References 74618 Conditional Probability 75518.1 Monty hall Confusion 75518.2 Definition and notation 75618. 3 The Four-Step method for Conditional probability 75818.4 Why Tree Diagrams Work 76018.5Thof Total Probability 76818.6 Simpsons Paradox 77018.7 Independence 77218.8 Mutual Independence 77418.9 Probability versus Confidence 77819 Random variables 80719.1 Random Variable examples 80719.2 Independence 8019.3 Distribution Functions 81019.4 Great Expectations 81919.5 Linearity of Expectation 83020 Deviation from the mean 86120.1 Markov's Theorem 86120.2 Chebyshevs Theorem 86420.3 Properties of Variance 86820.4 Estimation by Random Sampling 87420.5 Confidence in an Estimation 87720.6 Sums of random Variables 87920.7 Really Great Expectations 88821 Random walks 91321.1 Gambler's ruin 91321.2 Random walks on graphs 923V RecurrencesIntroduction 94722 Recurrences 943mcs-2017/3/23-23:53- page vill-#8VUContents22.1 The Towers of Hanoi 94322.2 Merge Sort 94622. 3 Linear Recurrences 95022.4 Divide-and-Conquer recurrences 95722.5 A Feel for recurrences 964Bibliography 971Glossary of Symbols 975Index 979mcs”-2017/3/23-23:53-page1一#9I Proofsmcs-2017/3/23-23:53-page2-#10