A couple of friends from Silicon Valley are taking the Stanford Algorithms course with me. One of the "readings" for the class is:
Mathematics for Computer Science Eric Lehman and Tom Leighton 2004 http://www.cs.princeton.edu/courses/archive/spr10/cos433/mathcs.pdf ... which is a surprisingly complete survey of most of your basic undergraduate math, done very well. -- Owen Here is the table of contents: Contents 1 What is a Proof? 15 1.1 Propositions..................................... 15 1.2 Axioms........................................ 19 1.3 LogicalDeductions ................................. 20 1.4 ExamplesofProofs ................................. 20 1.4.1 ATautology................................. 21 1.4.2 AProofbyContradiction ......................... 22 2 Induction I 23 2.1 AWarmupPuzzle.................................. 23 2.2 Induction....................................... 24 2.3 UsingInduction................................... 25 2.4 ADivisibilityTheorem............................... 28 2.5 AFaultyInductionProof.............................. 30 2.6 CourtyardTiling................................... 31 2.7 AnotherFaultyProof................................ 33 3 Induction II 35 3.1 GoodProofsandBadProofs............................ 35 3.2 APuzzle....................................... 36 3.3 Unstacking...................................... 40 3.3.1 StrongInduction .............................. 40 3.3.2 AnalyzingtheGame ............................ 41 4 Number Theory I 45 4.1 ATheoryoftheIntegers .............................. 46 4.2 Divisibility...................................... 46 4.2.1 Turing’sCode(Version1.0) ........................ 47 4.2.2 TheDivisionAlgorithm .......................... 50 4.2.3 BreakingTuring’sCode .......................... 51 4.3 ModularArithmetic................................. 51 4.3.1 CongruenceandRemainders....................... 51 4.3.2 Factsaboutremandmod......................... 52 4.3.3 Turing’sCode(Version2.0)........................ 54 4.3.4 CancellationModuloaPrime....................... 55 4.3.5 MultiplicativeInverses........................... 56 4.3.6 Fermat’sTheorem............................. 57 4.3.7 FindingInverseswithFermat’sTheorem................ 58 4.3.8 BreakingTuring’sCode—Again..................... 58 5 Number Theory II 61 5.1 DieHard....................................... 61 5.1.1 DeathbyInduction............................. 62 5.1.2 AGeneralTheorem............................. 63 5.1.3 TheGreatestCommonDivisor...................... 64 5.1.4 PropertiesoftheGreatestCommonDivisor............... 65 5.2 TheFundamentalTheoremofArithemtic .................... 67 5.3 ArithmeticwithanArbitraryModulus...................... 68 5.3.1 RelativePrimalityandPhi......................... 68 5.3.2 GeneralizingtoanArbitraryModulus.................. 70 5.3.3 Euler’sTheorem .............................. 71 6 Graph Theory 73 6.1 Introduction..................................... 73 6.1.1 Definitions.................................. 74 6.1.2 SexinAmerica ............................... 74 6.1.3 GraphVariations .............................. 76 6.1.4 ApplicationsofGraphs .......................... 77 6.1.5 SomeCommonGraphs .......................... 77 6.1.6 Isomorphism ................................ 79 6.2 Connectivity..................................... 80 6.2.1 ASimpleConnectivityTheorem ..................... 80 6.2.2 DistanceandDiameter........................... 81 6.2.3 Walks..................................... 83 6.3 AdjacencyMatrices................................. 83 6.4 Trees ......................................... 84 6.4.1 SpanningTrees ............................... 86 6.4.2 TreeVariations ............................... 87 7 Graph Theory II 89 7.1 ColoringGraphs................................... 89 7.1.1 k-Coloring.................................. 90 7.1.2 BipartiteGraphs .............................. 90 7.2 PlanarGraphs.................................... 91 7.2.1 Euler’sFormula............................... 93 7.2.2 ClassifyingPolyhedra ........................... 94 7.3 Hall’sMarriageTheorem.............................. 95 7.3.1 AFormalStatement ............................ 97 8 Communication Networks 99 8.1 CompleteBinaryTree................................ 99 8.1.1 LatencyandDiameter ...........................100 8.1.2 SwitchSize .................................101 8.1.3 SwitchCount ................................101 8.1.4 Congestion .................................101 8.2 2-DArray ......................................103 8.3 Butterfly .......................................104 8.4 Benes ̆Network ...................................106 9 Relations 111 9.0.1 RelationsonOneSet............................111 9.0.2 RelationsandDirectedGraphs ......................112 9.1 PropertiesofRelations ...............................112 9.2 EquivalenceRelations ...............................113 9.2.1 Partitions ..................................113 9.3 PartialOrders ....................................114 9.3.1 DirectedAcyclicGraphs..........................116 9.3.2 PartialOrdersandTotalOrders......................116 10 Sums, Approximations, and Asymptotics 119 10.1 The Value of an Annuity.............................. 119 10.1.1 TheFutureValueofMoney........................119 10.1.2 AGeometricSum..............................120 10.1.3 ReturnoftheAnnuityProblem......................121 10.1.4 InfiniteSums................................122 10.2 Variants of Geometric Sums............................ 123 10.3 Sums of Powers................................... 125 10.4 Approximating Sums................................ 126 10.4.1 IntegrationBounds.............................127 10.4.2 Taylor’sTheorem..............................128 10.4.3 BacktotheSum...............................130 10.4.4 AnotherIntegrationExample.......................131 11 Sums, Approximations, and Asymptotics II 133 11.1 Block Stacking.................................... 133 11.1.1 HarmonicNumbers............................135 11.2 Products.......................................137 11.3 Asymptotic Notation................................ 138 12 Recurrences I 143 12.1 TheTowersofHanoi ................................143 12.1.1 FindingaRecurrence............................144 12.1.2 ALowerBoundforTowersofHanoi...................145 12.1.3 Guess-and-Verify..............................146 12.1.4 ThePlug-and-ChugMethod .......................147 12.2 Merge Sort...................................... 149 12.2.1 TheAlgorithm...............................149 12.2.2 FindingaRecurrence............................150 12.2.3 SolvingtheRecurrence...........................150 12.3 More Recurrences.................................. 152 12.3.1 ASpeedyAlgorithm............................152 12.3.2 AVerificationProblem...........................153 12.3.3 AFalseProof................................154 12.3.4 AlteringtheNumberofSubproblems..................155 12.4 TheAkra-BazziMethod..............................155 12.4.1 SolvingDivideandConquerRecurrences................ 156 13 Recurrences II 159 13.1 AsymptoticNotationandInduction .......................159 13.2LinearRecurrences .................................160 13.2.1 GraduateStudentJobProspects .....................160 13.2.2 FindingaRecurrence............................161 13.2.3 SolvingtheRecurrence...........................162 13.2.4 JobProspects ................................164 13.3 GeneralLinearRecurrences ............................165 13.3.1 AnExample.................................167 13.4InhomogeneousRecurrences ...........................167 13.4.1 AnExample.................................168 13.4.2 HowtoGuessaParticularSolution ...................169 14 Counting I 173 14.1 CountingOneThingbyCountingAnother ...................174 14.1.1 Functions ..................................174 14.1.2 Bijections...................................175 14.1.3 TheBijectionRule .............................176 14.1.4 Sequences ..................................177 14.2 Two Basic Counting Rules............................. 178 14.2.1 TheSumRule................................178 14.2.2 TheProductRule..............................179 14.2.3 PuttingRulesTogether...........................180 14.3 MoreFunctions:InjectionsandSurjections...................181 14.3.1 ThePigeonholePrinciple.........................182 15 Counting II 187 15.1 The Generalized Product Rule........................... 188 15.1.1 DefectiveDollars..............................189 15.1.2 AChessProblem..............................189 15.1.3 Permutations................................190 15.2 The Division Rule.................................. 191 15.2.1 AnotherChessProblem..........................191 15.2.2 KnightsoftheRoundTable........................192 15.3 Inclusion-Exclusion................................. 193 15.3.1 UnionofTwoSets.............................194 15.3.2 UnionofThreeSets.............................195 15.3.3 UnionofnSets...............................196 15.4 TheGrandSchemeforCounting .........................197 16 Counting III 201 16.1 The Bookkeeper Rule................................ 201 16.1.1 20-MileWalks................................201 16.1.2 BitSequences................................202 16.1.3 k-elementSubsetsofann-elementSet..................202 16.1.4 AnAlternativeDerivation.........................203 16.1.5 WordofCaution ..............................203 16.2 BinomialTheorem .................................203 16.3 Poker Hands..................................... 204 16.3.1 Hands with a Four-of-a-Kind....................... 205 16.3.2 HandswithaFullHouse.........................205 16.3.3 HandswithTwoPairs...........................206 16.3.4 HandswithEverySuit...........................208 16.4 Magic Trick...................................... 209 16.4.1 TheSecret..................................209 16.4.2 TheRealSecret...............................211 16.4.3 SameTrickwithFourCards?.......................212 16.5 CombinatorialProof................................212 16.5.1 Boxing.................................... 213 16.5.2 CombinatorialProof............................214 17 Generating Functions 217 17.1 Generating Functions................................ 217 17.2 Operations on Generating Functions....................... 218 17.2.1 Scaling....................................218 17.2.2 Addition...................................219 17.2.3 Right Shifting................................ 220 17.2.4 Differentiation................................221 17.3 TheFibonacciSequence ..............................222 17.3.1 FindingaGeneratingFunction ......................222 17.3.2 FindingaClosedForm...........................224 17.4 Counting with Generating Functions....................... 225 17.4.1 ChoosingDistinctItemsfromaSet....................225 17.4.2 BuildingGeneratingFunctionsthatCount............... 225 17.4.3 ChoosingItemswithRepetition.....................227 17.5 An“Impossible”CountingProblem .......................229 18 Introduction to Probability 231 18.1 Monty Hall...................................... 231 18.1.1 TheFour-StepMethod...........................232 18.1.2 ClarifyingtheProblem...........................232 18.1.3 Step1:FindtheSampleSpace.......................233 18.1.4 Step2:DefineEventsofInterest.....................235 18.1.5 Step3:DetermineOutcomeProbabilities................236 18.1.6 Step4:ComputeEventProbabilities...................239 18.1.7 An Alternative Interpretation of the Monty Hall Problem....... 240 18.2 Strange Dice..................................... 240 18.2.1 AnalysisofStrangeDice..........................241 19 Conditional Probability 245 19.1 TheHaltingProblem ................................246 19.1.1 SolutiontotheHaltingProblem .....................246 19.1.2 WhyTreeDiagramsWork.........................248 19.2APosterioriProbabilities ..............................250 19.2.1 ACoinProblem...............................251 19.2.2 AVariantoftheTwoCoinsProblem...................252 19.3MedicalTesting ...................................254 19.4ConditionalProbabilityPitfalls ..........................256 19.4.1 CarnivalDice ................................256 19.4.2 OtherIdentities...............................258 19.4.3 DiscriminationLawsuit ..........................258 19.4.4 On-TimeAirlines..............................260 20 Independence 261 20.1 Independent Events................................. 261 20.1.1 Examples..................................261 20.1.2 WorkingwithIndependence.......................262 20.1.3 SomeIntuition...............................262 20.1.4 AnExperimentwithTwoCoins.....................263 20.1.5 AVariationoftheTwo-CoinExperiment................ 264 20.2 MutualIndependence...............................266 20.2.1 DNATesting................................267 20.2.2 PairwiseIndependence..........................268 20.3TheBirthdayParadox...............................270 20.3.1 TheFour-StepMethod...........................270 20.3.2 AnAlternativeApproach.........................272 20.3.3 AnUpperBound..............................272 20.3.4 ALowerBound...............................274 20.3.5 TheBirthdayPrinciple...........................275 21 Random Variables 277 21.1 Random Variables.................................. 277 21.1.1 IndicatorRandomVariables........................278 21.1.2 RandomVariablesandEvents......................278 21.1.3 ConditionalProbability..........................279 21.1.4 Independence................................280 21.1.5 AnExamplewithDice...........................281 21.2 Probability Distributions.............................. 282 21.2.1 BernoulliDistribution...........................284 21.2.2 UniformDistribution............................284 21.2.3 TheNumbersGame............................285 21.2.4 BinomialDistribution...........................287 21.2.5 Approximating the Cumulative Binomial Distribution Function... 290 21.3 Philosophy of Polling................................ 291 22 Expected Value I 293 22.1 Betting on Coins................................... 293 22.2 EquivalentDefinitionsofExpectation......................296 22.2.1 MeanTimetoFailure............................297 22.2.2 MakingaBabyGirl.............................298 22.3 AnExpectationParadox ..............................298 22.4 LinearityofExpectation ..............................300 22.4.1 ExpectedValueofTwoDice........................301 22.4.2 TheHat-CheckProblem..........................302 22.4.3 TheChineseAppetizerProblem .....................303 23 Expected Value II 305 23.1 TheExpectedNumberofEventsthatHappen.................. 305 23.1.1 ACoinProblem—theEasyWay.....................306 23.1.2 TheHardWay................................306 23.2 TheCouponCollectorProblem..........................307 23.2.1 ASolutionUsingLinearityofExpectation............... 307 23.3 Expected Value of a Product............................ 309 23.3.1 TheProductofTwoIndependentDice..................309 23.3.2 TheProductofTwoDependentDice...................310 23.3.3 Corollaries..................................310 24 Weird Happenings 315 24.1 The New Grading Policy.............................. 316 24.1.1 Markov’sInequality............................316 24.1.2 LimitationsoftheMarkovInequality..................317 24.2 The Tip of the Tail.................................. 317 24.2.1 UpperBound:TheUnionBound.....................318 24.2.2 LowerBound:“Murphy’sLaw”.....................318 24.2.3 TheBigPicture...............................319 24.3 ChernoffBounds ..................................320 24.3.1 MITAdmissions ..............................321 24.3.2 ProvingChernoffBounds .........................322 24.4Hashing .......................................324 24.4.1 TheFirstCollision .............................325 24.4.2 NRecordsinNBins ............................325 24.4.3 AllBinsFull.................................326 25 Random Walks 327 25.1 ABug’sLife.....................................327 25.1.1 ASimplerProblem.............................328 25.1.2 ABigIsland.................................329 25.1.3 LifeExpectancy...............................332 25.2TheGambler’sRuin................................334 25.2.1 FindingaRecurrence............................335 25.2.2 SolvingtheRecurrence...........................335 25.2.3 InterpretingtheSolution..........................337 25.2.4 SomeIntuition...............................337 25.3 Pass the Broccoli................................... 338
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org
