Mathematics for Computer Science

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 Contents I Proofs Introduction 1 What is a Proof? 2 The Well Ordering Principle 3 Logical Formulas 4 Mathematical Data Types 5 Induction 6 Recursive Data Types 7 Infinite Sets 8 Number Theory II Structures Introduction 9 Directed graphs & Partial Orders 10 Communication Networks 11 Simple Graphs 12 Planar Graphs III Counting Introduction 13 Sums and Asymptotics 14 Cardinality Rules 15 Generating Functions IV Probability Introduction 16 Events and Probability Spaces 17 Random Variables 18 Deviation from the Mean 19 Random Processes V Recurrences Introduction 20 Recurrences Bibliography Index Glossary of Symbols Contents I Proofs 1 What is a Proof? 1.1 Propositions 1.2 Predicates 1.3 The Axiomatic Method 1.4 Our Axioms 1.5 Proving an Implication 1.6 Proving an “If and Only If” 1.7 Proof by Cases 1.8 Proof by Contradiction 1.9 Good Proofs in Practice 2 The Well Ordering Principle 2.1 Well Ordering Proofs 2.2 Template for Well Ordering Proofs 2.3 Factoring into Primes 2.4 Well Ordered Sets 3 Logical Formulas 3.1 Propositions from Propositions 3.2 Propositional Logic in Computer Programs 3.3 Equivalence and Validity 3.4 The Algebra of Propositions 3.5 The SAT Problem 3.6 Predicate Formulas 4 Mathematical Data Types 4.1 Sets 4.2 Sequences 4.3 Functions 4.4 Binary' Relations 4.5 Finite Cardinality 5 Induction 5.1 Ordinary Induction 5.2 Strong Induction 5.3 Strong Induction vs. Induction vs. Well Ordering 5.4 State Machines 6 Recursive Data Types 6.1 Recursive Definitions and Structural Induction 6.2 Strings of Matched Brackets 6.3 Recursive Functions on Nonnegative Integers 6.4 Arithmetic Expressions 6.5 Induction in Computer Science 7 Infinite Sets 7.1 Infinite Cardinality 7.2 The Halting Problem 7.3 The Logic of Sets 7.4 Does All This Really Work? 8 Number Theory 8.1 Divisibility 8.2 The Greatest Common Divisor 8.3 Prime Mysteries 8.4 The Fundamental Theorem of Arithmetic 8.5 Alan Turing 8.6 Modular Arithmetic 8.7 Remainder Arithmetic 8.8 Turing’s Code (Version 2.0) 8.9 Multiplicative Inverses and Cancelling 8.10 Euler’s Theorem 8.11 RSA Public Key Encryption 8.12 What has SAT got to do with it? II Structures 9 Directed graphs & Partial Orders 9.1 Digraphs & Vertex Degrees 9.2 Adjacency Matrices 9.3 Walk Relations 9.4 Directed Acyclic Graphs & Partial Orders 9.5 Weak Partial Orders 9.6 Representing Partial Orders by Set Containment 9.7 Path-Total Orders 9.8 Product Orders 9.9 Scheduling 9.10 Equivalence Relations 9.11 Summary of Relational Properties 10 Communication Networks 10.1 Complete Binary Tree 10.2 Routing Problems 10.3 Network Diameter 10.4 Switch Count 10.5 Network Latency 10.6 Congestion 10.7 2-D Array 10.8 Butterfly 10.9 BeneS Network 11 Simple Graphs 11.1 Vertex Adjacency and Degrees 11.2 Sexual Demographics in America 11.3 Some Common Graphs 11.4 Isomorphism 11.5 Bipartite Graphs & Matchings 11.6 The Stable Marriage Problem 11.7 Coloring 11.8 Getting from u to v in a Graph 11.9 Connectivity 11.10 Odd Cycles and 2-Colorability 11.11 Forests & Trees 12 Planar Graphs 12.1 Drawing Graphs in the Plane 12.2 De finitions of Planar Graphs 12.3 Euler’s Formula 12.4 Bounding the Number of Edges in a Planar Graph 12.5 Returning to K5 and 3 12.6 Coloring Planar Graphs 12.7 Classifying Polyhedra 12.8 Another Characterization for Planar Graphs III Counting 13 Sums and Asymptotics 13.1 The Value of an Annuity 13.2 Sums of Powers 13.3 Approximating Sums 13.4 Hanging Out Over the Edge 13.5 Products 13.6 Double Trouble 13.7 Asymptotic Notation 14 Cardinality Rules 14.1 Counting One Thing by Counting Another 14.2 Counting Sequences 14.3 The Generalized Product Rule 14.4 The Division Rule 14.5 Counting Subsets 14.6 Sequences with Repetitions 14.7 Counting Practice: Poker Hands 14.8 The Pigeonhole Principle 14.9 Inclusion-Exclusion 14.10 Combinatorial Proofs 15 Generating Functions 15.1 Infinite Series 15.2 Counting with Generating Functions 15.3 Partial Fractions 15.4 Solving Linear Recurrences 15.5 Formal Power Series IV Probability 16 Events and Probability Spaces 16.1 Let's Make a Deal 16.2 The Four Step Method 16.3 Strange Dice 16.4 Set Theory and Probability 16.5 Conditional Probability 16.6 Independence 17 Random Variables 17.1 Random Variable Examples 17.2 Independence 17.3 Distribution Functions 17.4 Great Expectations 17.5 Linearity of Expectation 18 Deviation from the Mean 18.1 Why the Mean? 18.2 Markov’s Theorem 18.3 Chebyshev’s Theorem 18.4 Properties of Variance 18.5 Estimation by Random Sampling 18.6 Confidence versus Probability 18.7 Sums of Random Variables 18.8 Really Great Expectations 19 Random Processes 19.1 Gamblers’Ruin 19.2 Random Walks on Graphs V Recurrences 20 Recurrences 20.1 The Towers of Hanoi 20.2 Merge Sort 20.3 Linear Recurrences 20.4 Divide-and-Conquer Recurrences 20.5 A Feel for Recurrences Bibliography Index