Mathematics for Computer Science

Description

This text explains how to use mathematical models and methods to analyze problems that arise in computer science. The subject offers an introduction to Discrete Mathematics oriented toward Computer Science and Engineering, adnd covers: Fundamental concepts of Mathematics: definitions, proofs, sets, functions, relations; Discrete structures: graphs, state machines, modular arithmetic, counting; Discrete probability theory.Readers will be able- to reason mathematically about basic data types and structures used in computer algorithms and systems; distinguish rigorous definitions and conclusions from merely plausible ones; synthesize elementary proofs, especially proofs by induction.- to model and analyze computational processes using analytic and combinatorial methods.- to apply principles of discrete probability to calculate probabilities and expectations of simple random processes.Brief ContentsI ProofsIntroduction1 What is a Proof?2 The Well Ordering Principle3 Logical Formulas4 Mathematical Data Types5 Induction6 Recursive Data Types7 Infinite Sets8 Number TheoryII StructuresIntroduction9 Directed graphs & Partial Orders10 Communication Networks11 Simple Graphs12 Planar GraphsIII CountingIntroduction13 Sums and Asymptotics14 Cardinality Rules15 Generating FunctionsIV ProbabilityIntroduction16 Events and Probability Spaces17 Random Variables18 Deviation from the Mean19 Random ProcessesV RecurrencesIntroduction20 RecurrencesBibliographyIndexGlossary of SymbolsContentsI Proofs1 What is a Proof?1.1 Propositions1.2 Predicates1.3 The Axiomatic Method1.4 Our Axioms1.5 Proving an Implication1.6 Proving an “If and Only If”1.7 Proof by Cases1.8 Proof by Contradiction1.9 Good Proofs in Practice2 The Well Ordering Principle2.1 Well Ordering Proofs2.2 Template for Well Ordering Proofs2.3 Factoring into Primes2.4 Well Ordered Sets3 Logical Formulas3.1 Propositions from Propositions3.2 Propositional Logic in Computer Programs3.3 Equivalence and Validity3.4 The Algebra of Propositions3.5 The SAT Problem3.6 Predicate Formulas4 Mathematical Data Types4.1 Sets4.2 Sequences4.3 Functions4.4 Binary' Relations4.5 Finite Cardinality5 Induction5.1 Ordinary Induction5.2 Strong Induction5.3 Strong Induction vs. Induction vs. Well Ordering5.4 State Machines6 Recursive Data Types6.1 Recursive Definitions and Structural Induction6.2 Strings of Matched Brackets6.3 Recursive Functions on Nonnegative Integers6.4 Arithmetic Expressions6.5 Induction in Computer Science7 Infinite Sets7.1 Infinite Cardinality7.2 The Halting Problem7.3 The Logic of Sets7.4 Does All This Really Work?8 Number Theory8.1 Divisibility8.2 The Greatest Common Divisor8.3 Prime Mysteries8.4 The Fundamental Theorem of Arithmetic8.5 Alan Turing8.6 Modular Arithmetic8.7 Remainder Arithmetic8.8 Turing’s Code (Version 2.0)8.9 Multiplicative Inverses and Cancelling8.10 Euler’s Theorem8.11 RSA Public Key Encryption8.12 What has SAT got to do with it?II Structures9 Directed graphs & Partial Orders9.1 Digraphs & Vertex Degrees9.2 Adjacency Matrices9.3 Walk Relations9.4 Directed Acyclic Graphs & Partial Orders9.5 Weak Partial Orders9.6 Representing Partial Orders by Set Containment9.7 Path-Total Orders9.8 Product Orders9.9 Scheduling9.10 Equivalence Relations9.11 Summary of Relational Properties10 Communication Networks10.1 Complete Binary Tree10.2 Routing Problems10.3 Network Diameter10.4 Switch Count10.5 Network Latency10.6 Congestion10.7 2-D Array10.8 Butterfly10.9 BeneS Network11 Simple Graphs11.1 Vertex Adjacency and Degrees11.2 Sexual Demographics in America11.3 Some Common Graphs11.4 Isomorphism11.5 Bipartite Graphs & Matchings11.6 The Stable Marriage Problem11.7 Coloring11.8 Getting from u to v in a Graph11.9 Connectivity11.10 Odd Cycles and 2-Colorability11.11 Forests & Trees12 Planar Graphs12.1 Drawing Graphs in the Plane12.2 De finitions of Planar Graphs12.3 Euler’s Formula12.4 Bounding the Number of Edges in a Planar Graph12.5 Returning to K5 and 312.6 Coloring Planar Graphs12.7 Classifying Polyhedra12.8 Another Characterization for Planar GraphsIII Counting13 Sums and Asymptotics13.1 The Value of an Annuity13.2 Sums of Powers13.3 Approximating Sums13.4 Hanging Out Over the Edge13.5 Products13.6 Double Trouble13.7 Asymptotic Notation14 Cardinality Rules14.1 Counting One Thing by Counting Another14.2 Counting Sequences14.3 The Generalized Product Rule14.4 The Division Rule14.5 Counting Subsets14.6 Sequences with Repetitions14.7 Counting Practice: Poker Hands14.8 The Pigeonhole Principle14.9 Inclusion-Exclusion14.10 Combinatorial Proofs15 Generating Functions15.1 Infinite Series15.2 Counting with Generating Functions15.3 Partial Fractions15.4 Solving Linear Recurrences15.5 Formal Power SeriesIV Probability16 Events and Probability Spaces16.1 Let's Make a Deal16.2 The Four Step Method16.3 Strange Dice16.4 Set Theory and Probability16.5 Conditional Probability16.6 Independence17 Random Variables17.1 Random Variable Examples17.2 Independence17.3 Distribution Functions17.4 Great Expectations17.5 Linearity of Expectation18 Deviation from the Mean18.1 Why the Mean?18.2 Markov’s Theorem18.3 Chebyshev’s Theorem18.4 Properties of Variance18.5 Estimation by Random Sampling18.6 Confidence versus Probability18.7 Sums of Random Variables18.8 Really Great Expectations19 Random Processes19.1 Gamblers’Ruin19.2 Random Walks on GraphsV Recurrences20 Recurrences20.1 The Towers of Hanoi20.2 Merge Sort20.3 Linear Recurrences20.4 Divide-and-Conquer Recurrences20.5 A Feel for RecurrencesBibliographyIndex