“mcs” — 2017/3/6 — 12:54 — page i — #1 Mathematics for Computer Science revisedMonday6th March,2017,12:54 Eric Lehman GoogleInc. F Thomson Leighton DepartmentofMathematics andtheComputerScienceandAILaboratory, MassachussettsInstituteofTechnology; AkamaiTechnologies Albert R Meyer DepartmentofElectricalEngineeringandComputerScience andtheComputerScienceandAILaboratory, MassachussettsInstituteofTechnology 2016,EricLehman,FTomLeighton,AlbertRMeyer.Thisworkisavailableunderthe termsoftheCreativeCommonsAttribution-ShareAlike3.0license. “mcs” — 2017/3/6 — 12:54 — page ii — #2 “mcs” — 2017/3/6 — 12:54 — page iii — #3 Contents I Proofs Introduction 3 0.1 References 4 1 WhatisaProof? 5 1.1 Propositions 5 1.2 Predicates 8 1.3 TheAxiomaticMethod 8 1.4 OurAxioms 9 1.5 ProvinganImplication 11 1.6 Provingan“IfandOnlyIf” 13 1.7 ProofbyCases 15 1.8 ProofbyContradiction 16 1.9 Good ProofsinPractice 17 1.10 References 19 2 TheWellOrderingPrinciple 29 2.1 WellOrderingProofs 29 2.2 TemplateforWellOrderingProofs 30 2.3 FactoringintoPrimes 32 2.4 WellOrderedSets 33 3 LogicalFormulas 45 3.1 PropositionsfromPropositions 46 3.2 PropositionalLogicinComputerPrograms 50 3.3 EquivalenceandValidity 52 3.4 TheAlgebraofPropositions 55 3.5 TheSATProblem 60 3.6 PredicateFormulas 61 3.7 References 66 4 MathematicalDataTypes 91 4.1 Sets 91 4.2 Sequences 96 4.3 Functions 97 4.4 BinaryRelations 99 4.5 FiniteCardinality 103 “mcs” — 2017/3/6 — 12:54 — page iv — #4 iv Contents 5 Induction 123 5.1 OrdinaryInduction 123 5.2 StrongInduction 132 5.3 StrongInductionvs.Inductionvs.WellOrdering 139 6 StateMachines 159 6.1 StatesandTransitions 159 6.2 TheInvariantPrinciple 160 6.3 PartialCorrectness&Termination 168 6.4 TheStableMarriageProblem 173 7 RecursiveDataTypes 203 7.1 RecursiveDefinitionsandStructuralInduction 203 7.2 StringsofMatchedBrackets 207 7.3 RecursiveFunctionsonNonnegativeIntegers 211 7.4 ArithmeticExpressions 213 7.5 InductioninComputerScience 218 8 InfiniteSets 245 8.1 InfiniteCardinality 246 8.2 TheHaltingProblem 255 8.3 TheLogicofSets 259 8.4 DoesAllThisReallyWork? 262 II Structures Introduction 287 9 NumberTheory 289 9.1 Divisibility 289 9.2 TheGreatestCommonDivisor 294 9.3 PrimeMysteries 301 9.4 TheFundamentalTheoremofArithmetic 303 9.5 AlanTuring 306 9.6 ModularArithmetic 310 9.7 RemainderArithmetic 312 9.8 Turing’sCode(Version2.0) 315 9.9 MultiplicativeInversesandCancelling 317 9.10 Euler’sTheorem 321 9.11 RSAPublicKeyEncryption 326 9.12 WhathasSATgottodowithit? 328 “mcs” — 2017/3/6 — 12:54 — page v — #5 v Contents 9.13 References 329 10 Directedgraphs&PartialOrders 367 10.1 VertexDegrees 369 10.2 WalksandPaths 370 10.3 AdjacencyMatrices 373 10.4 WalkRelations 376 10.5 DirectedAcyclicGraphs&Scheduling 377 10.6 PartialOrders 385 10.7 RepresentingPartialOrdersbySetContainment 389 10.8 LinearOrders 390 10.9 ProductOrders 390 10.10EquivalenceRelations 391 10.11SummaryofRelationalProperties 393 11 CommunicationNetworks 425 11.1 Routing 425 11.2 RoutingMeasures 426 11.3 NetworkDesigns 429 12 SimpleGraphs 445 12.1 VertexAdjacencyandDegrees 445 12.2 SexualDemographicsinAmerica 447 12.3 SomeCommonGraphs 449 12.4 Isomorphism 451 12.5 BipartiteGraphs&Matchings 453 12.6 Coloring 458 12.7 SimpleWalks 463 12.8 Connectivity 465 12.9 Forests&Trees 470 12.10References 478 13 PlanarGraphs 517 13.1 DrawingGraphsinthePlane 517 13.2 DefinitionsofPlanarGraphs 517 13.3 Euler’sFormula 528 13.4 BoundingtheNumberofEdgesinaPlanarGraph 529 13.5 ReturningtoK andK 530 5 3;3 13.6 ColoringPlanarGraphs 531 13.7 ClassifyingPolyhedra 533 13.8 AnotherCharacterizationforPlanarGraphs 536 “mcs” — 2017/3/6 — 12:54 — page vi — #6 vi Contents III Counting Introduction 545 14 SumsandAsymptotics 547 14.1 TheValueofanAnnuity 548 14.2 SumsofPowers 554 14.3 ApproximatingSums 556 14.4 HangingOutOvertheEdge 560 14.5 Products 566 14.6 DoubleTrouble 569 14.7 AsymptoticNotation 572 15 CardinalityRules 597 15.1 CountingOneThingbyCountingAnother 597 15.2 CountingSequences 598 15.3 TheGeneralizedProductRule 601 15.4 TheDivisionRule 605 15.5 CountingSubsets 608 15.6 SequenceswithRepetitions 610 15.7 CountingPractice: PokerHands 613 15.8 ThePigeonholePrinciple 618 15.9 Inclusion-Exclusion 627 15.10CombinatorialProofs 633 15.11References 637 16 GeneratingFunctions 675 16.1 InfiniteSeries 675 16.2 CountingwithGeneratingFunctions 677 16.3 PartialFractions 683 16.4 SolvingLinearRecurrences 686 16.5 FormalPowerSeries 691 16.6 References 694 IV Probability Introduction 713 17 EventsandProbabilitySpaces 715 17.1 Let’sMakeaDeal 715 “mcs” — 2017/3/6 — 12:54 — page vii — #7 vii Contents 17.2 TheFourStepMethod 716 17.3 StrangeDice 725 17.4 TheBirthdayPrinciple 732 17.5 SetTheoryandProbability 734 17.6 References 738 18 ConditionalProbability 747 18.1 MontyHallConfusion 747 18.2 DefinitionandNotation 748 18.3 TheFour-StepMethodforConditionalProbability 750 18.4 WhyTreeDiagramsWork 752 18.5 TheLawofTotalProbability 760 18.6 Simpson’sParadox 762 18.7 Independence 764 18.8 MutualIndependence 766 18.9 ProbabilityversusConfidence 770 19 RandomVariables 799 19.1 RandomVariableExamples 799 19.2 Independence 801 19.3 DistributionFunctions 802 19.4 GreatExpectations 811 19.5 LinearityofExpectation 822 20 DeviationfromtheMean 853 20.1 Markov’sTheorem 853 20.2 Chebyshev’sTheorem 856 20.3 PropertiesofVariance 860 20.4 EstimationbyRandomSampling 866 20.5 ConfidenceinanEstimation 869 20.6 SumsofRandomVariables 871 20.7 ReallyGreatExpectations 880 21 RandomWalks 905 21.1 Gambler’sRuin 905 21.2 RandomWalksonGraphs 915 V Recurrences Introduction 933 22 Recurrences 935 “mcs” — 2017/3/6 — 12:54 — page viii — #8 viii Contents 22.1 TheTowersofHanoi 935 22.2 MergeSort 938 22.3 LinearRecurrences 942 22.4 Divide-and-ConquerRecurrences 949 22.5 AFeelforRecurrences 956 Bibliography 963 GlossaryofSymbols 967 Index 971 “mcs” — 2017/3/6 — 12:54 — page 1 — #9 I Proofs “mcs” — 2017/3/6 — 12:54 — page 2 — #10