Mathematics for Computer Science - IIT Guwahati

"mcs" -- 2011/5/9 -- 20:49 -- page i -- #1

Mathematics for Computer Science

revised Monday 9th May, 2011, 20:49

Eric Lehman

Google Inc.

F Thomson Leighton

Department of Mathematics and CSAIL, MIT Akamai Technologies

Albert R Meyer

Massachusets Institute of Technology

Creative Commons

2011, Eric Lehman, F Tom Leighton, Albert R Meyer .

"mcs" -- 2011/5/9 -- 20:49 -- page ii -- #2

"mcs" -- 2011/5/9 -- 20:49 -- page iii -- #3

Contents

I Proofs

1 What is a Proof? 7

1.1 Propositions 7 1.2 Predicates 9 1.3 The Axiomatic Method 10 1.4 Our Axioms 11 1.5 Proving an Implication 13 1.6 Proving an "If and Only If" 15 1.7 Proof by Cases 17 1.8 Proof by Contradiction 18 1.9 Good Proofs in Practice 19

2 The Well Ordering Principle 25

2.1 Well Ordering Proofs 25 2.2 Template for Well Ordering Proofs 26 2.3 Summing the Integers 26 2.4 Factoring into Primes 28

3 Logical Formulas 35

3.1 Propositions from Propositions 36 3.2 Propositional Logic in Computer Programs 39 3.3 Equivalence and Validity 42 3.4 The Algebra of Propositions 44 3.5 The SAT Problem 49 3.6 Predicate Formulas 50

4 Mathematical Data Types 67

4.1 Sets 67 4.2 Sequences 70 4.3 Functions 71 4.4 Binary Relations 73

5 Infinite Sets 87

5.1 Finite Cardinality 88 5.2 Infinite Cardinality 90 5.3 The Halting Problem 95 5.4 The Logic of Sets 98

"mcs" -- 2011/5/9 -- 20:49 -- page iv -- #4

iv

Contents

5.5 Does All This Really Work? 101

6 Induction 113

6.1 Ordinary Induction 113 6.2 State Machines 122 6.3 Strong Induction 134 6.4 Strong Induction vs. Induction vs. Well Ordering 138

7 Recursive Data Types 159

7.1 Recursive Definitions and Structural Induction 159 7.2 Strings of Matched Brackets 163 7.3 Recursive Functions on Nonnegative Integers 166 7.4 Arithmetic Expressions 169 7.5 Induction in Computer Science 174

8 Number Theory 183

8.1 Divisibility 183 8.2 The Greatest Common Divisor 189 8.3 The Fundamental Theorem of Arithmetic 195 8.4 Alan Turing 197 8.5 Modular Arithmetic 201 8.6 Arithmetic with a Prime Modulus 204 8.7 Arithmetic with an Arbitrary Modulus 209 8.8 The RSA Algorithm 214 8.9 What has SAT got to do with it? 216

II Structures

9 Directed graphs & Partial Orders 233

9.1 Digraphs & Vertex Degrees 235 9.2 Digraph Walks and Paths 236 9.3 Adjacency Matrices 239 9.4 Path Relations 242 9.5 Directed Acyclic Graphs & Partial Orders 243 9.6 Weak Partial Orders 246 9.7 Representing Partial Orders by Set Containment 247 9.8 Path-Total Orders 248 9.9 Product Orders 249 9.10 Scheduling 250 9.11 Equivalence Relations 256

"mcs" -- 2011/5/9 -- 20:49 -- page v -- #5

v

Contents

9.12 Summary of Relational Properties 257

10 Communication Networks 279

10.1 Complete Binary Tree 279 10.2 Routing Problems 279 10.3 Network Diameter 280 10.4 Switch Count 281 10.5 Network Latency 282 10.6 Congestion 282 10.7 2-D Array 283 10.8 Butterfly 285 10.9 Benes Network 287

11 Simple Graphs 299

11.1 Vertex Adjacency and Degrees 299 11.2 Sexual Demographics in America 301 11.3 Some Common Graphs 303 11.4 Isomorphism 305 11.5 Bipartite Graphs & Matchings 307 11.6 The Stable Marriage Problem 312 11.7 Coloring 319 11.8 Getting from u to v in a Graph 324 11.9 Connectivity 325 11.10 Odd Cycles and 2-Colorability 329 11.11 Forests & Trees 330

12 Planar Graphs 361

12.1 Drawing Graphs in the Plane 361 12.2 Definitions of Planar Graphs 361 12.3 Euler's Formula 371 12.4 Bounding the Number of Edges in a Planar Graph 372 12.5 Returning to K5 and K3;3 373 12.6 Another Characterization for Planar Graphs 374 12.7 Coloring Planar Graphs 375 12.8 Classifying Polyhedra 377

13 State Machines 387

13.1 The Alternating Bit Protocol 387 13.2 Reasoning About While Programs 390

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download