Mathematics for Computer Science

I Proofs......Page 9
Problem 0.1......Page 12
Problem 0.3......Page 13
1.1 Propositions......Page 15
1.2 Predicates......Page 17
1.3 The Axiomatic Method......Page 18
1.4 Our Axioms......Page 19
1.5 Proving an Implication......Page 21
1.6 Proving an ``If and Only If''......Page 23
1.7 Proof by Cases......Page 25
1.8 Proof by Contradiction......Page 26
1.9 Good Proofs in Practice......Page 27
Problem 1.3......Page 29
Problem 1.6......Page 30
Problem 1.8......Page 31
2.1 Well Ordering Proofs......Page 33
2.3 Summing the Integers......Page 34
2.4 Factoring into Primes......Page 36
Problem 2.2......Page 37
Problem 2.4......Page 38
Problem 2.6......Page 39
Problem 2.8......Page 41
3 Logical Formulas......Page 43
3.1 Propositions from Propositions......Page 44
3.2 Propositional Logic in Computer Programs......Page 47
Problem 3.1......Page 49
3.3 Equivalence and Validity......Page 50
3.4 The Algebra of Propositions......Page 52
3.5 The SAT Problem......Page 57
3.6 Predicate Formulas......Page 58
Problem 3.3......Page 63
Problem 3.5......Page 64
Problem 3.6......Page 65
Problem 3.7......Page 66
Problem 3.9......Page 68
Problem 3.12......Page 69
Problem 3.13......Page 70
Problem 3.14......Page 71
Problem 3.17......Page 72
Problem 3.19......Page 73
4.1 Sets......Page 75
4.2 Sequences......Page 78
4.3 Functions......Page 79
4.4 Binary Relations......Page 81
Problem 4.1......Page 85
Problem 4.3......Page 86
Problem 4.5......Page 87
Problem 4.8......Page 88
Problem 4.9......Page 89
Problem 4.11......Page 90
Problem 4.12......Page 91
Problem 4.16......Page 92
5 Infinite Sets......Page 95
5.1 Finite Cardinality......Page 96
5.2 Infinite Cardinality......Page 98
5.3 The Halting Problem......Page 103
5.4 The Logic of Sets......Page 106
5.5 Does All This Really Work?......Page 109
Problem 5.3......Page 111
Problem 5.5......Page 112
Problem 5.6......Page 113
Problem 5.10......Page 114
Problem 5.11......Page 115
Problem 5.12......Page 116
Problem 5.13......Page 117
Problem 5.15......Page 118
Problem 5.16......Page 119
6.1 Ordinary Induction......Page 121
6.2 State Machines......Page 130
6.3 Strong Induction......Page 142
6.4 Strong Induction vs. Induction vs. Well Ordering......Page 146
Problem 6.2......Page 147
Problem 6.5......Page 148
Problem 6.7......Page 149
Problem 6.9......Page 150
Problem 6.10......Page 151
Problem 6.11......Page 152
Problem 6.13......Page 153
Problem 6.14......Page 154
Problem 6.15......Page 155
Problem 6.16......Page 156
Problem 6.18......Page 157
Problem 6.19......Page 159
Problem 6.20......Page 160
Problem 6.21......Page 161
Problem 6.24......Page 162
Problem 6.25......Page 163
Problem 6.27......Page 164
Problem 6.28......Page 165
7.1 Recursive Definitions and Structural Induction......Page 167
7.2 Strings of Matched Brackets......Page 171
7.3 Recursive Functions on Nonnegative Integers......Page 174
7.4 Arithmetic Expressions......Page 177
Problem 7.3......Page 182
Problem 7.4......Page 183
Problem 7.5......Page 184
Problem 7.7......Page 185
Problem 7.9......Page 186
Problem 7.10......Page 187
Problem 7.12......Page 189
Problem 7.15......Page 190
8.1 Divisibility......Page 193
8.2 The Greatest Common Divisor......Page 199
8.3 The Fundamental Theorem of Arithmetic......Page 205
8.4 Alan Turing......Page 207
8.5 Modular Arithmetic......Page 211
8.6 Arithmetic with a Prime Modulus......Page 214
8.7 Arithmetic with an Arbitrary Modulus......Page 219
8.8 The RSA Algorithm......Page 224
Problem 8.1......Page 226
Problem 8.4......Page 227
Problem 8.7......Page 228
Problem 8.10......Page 229
Problem 8.12......Page 230
Problem 8.17......Page 231
Problem 8.18......Page 232
Problem 8.19......Page 233
Problem 8.20......Page 234
Problem 8.24......Page 235
Problem 8.26......Page 236
Problem 8.27......Page 238
II Structures......Page 241
9 Directed graphs & Partial Orders......Page 245
9.1 Digraphs & Vertex Degrees......Page 247
9.2 Digraph Walks and Paths......Page 248
9.3 Adjacency Matrices......Page 251
9.4 Path Relations......Page 254
9.5 Directed Acyclic Graphs & Partial Orders......Page 255
9.6 Weak Partial Orders......Page 258
9.7 Representing Partial Orders by Set Containment......Page 259
9.8 Path-Total Orders......Page 260
9.9 Product Orders......Page 261
9.10 Scheduling......Page 262
9.11 Equivalence Relations......Page 268
9.12 Summary of Relational Properties......Page 269
Problem 9.2......Page 271
Problem 9.3......Page 272
Problem 9.5......Page 273
Problem 9.8......Page 274
Problem 9.10......Page 275
Problem 9.11......Page 276
Problem 9.13......Page 278
Problem 9.14......Page 279
Problem 9.16......Page 280
Problem 9.22......Page 281
Problem 9.24......Page 282
Problem 9.28......Page 283
Problem 9.29......Page 284
Problem 9.31......Page 286
Problem 9.32......Page 287
Problem 9.33......Page 288
Problem 9.35......Page 289
10.2 Routing Problems......Page 291
10.3 Network Diameter......Page 292
10.4 Switch Count......Page 293
10.6 Congestion......Page 294
10.7 2-D Array......Page 295
10.8 Butterfly......Page 297
10.9 Benes Network......Page 299
Problem 10.1......Page 304
Problem 10.2......Page 305
Problem 10.4......Page 306
Problem 10.6......Page 307
Problem 10.8......Page 309
11.1 Vertex Adjacency and Degrees......Page 311
11.2 Sexual Demographics in America......Page 313
11.3 Some Common Graphs......Page 315
11.4 Isomorphism......Page 317
11.5 Bipartite Graphs & Matchings......Page 319
11.6 The Stable Marriage Problem......Page 324
11.7 Coloring......Page 331
11.8 Getting from u to v in a Graph......Page 336
11.9 Connectivity......Page 337
11.10 Odd Cycles and 2-Colorability......Page 341
11.11 Forests & Trees......Page 342
Problem 11.2......Page 351
Problem 11.5......Page 352
Problem 11.6......Page 354
Problem 11.8......Page 355
Problem 11.9......Page 356
Problem 11.11......Page 357
Problem 11.14......Page 358
Problem 11.16......Page 359
Problem 11.18......Page 360
Problem 11.21......Page 361
Problem 11.23......Page 362
Problem 11.24......Page 363
Problem 11.25......Page 364
Problem 11.28......Page 365
Problem 11.29......Page 366
Problem 11.30......Page 367
Problem 11.32......Page 368
Problem 11.33......Page 369
Problem 11.35......Page 370
Problem 11.38......Page 371
12.2 Definitions of Planar Graphs......Page 373
12.3 Euler's Formula......Page 383
12.4 Bounding the Number of Edges in a Planar Graph......Page 384
12.5 Returning to K5 and K3,3......Page 385
12.6 Another Characterization for Planar Graphs......Page 386
12.7 Coloring Planar Graphs......Page 387
12.8 Classifying Polyhedra......Page 389
Problem 12.2......Page 392
Problem 12.4......Page 393
Problem 12.6......Page 394
Problem 12.8......Page 396
13.1 The Alternating Bit Protocol......Page 399
13.2 Reasoning About While Programs......Page 402
Problem 13.1......Page 408
III Counting......Page 409
14 Sums and Asymptotics......Page 413
14.1 The Value of an Annuity......Page 414
14.2 Sums of Powers......Page 420
14.3 Approximating Sums......Page 422
14.4 Hanging Out Over the Edge......Page 426
14.5 Products......Page 438
14.6 Double Trouble......Page 440
14.7 Asymptotic Notation......Page 443
Problem 14.3......Page 449
Problem 14.6......Page 450
Problem 14.8......Page 452
Problem 14.10......Page 453
Problem 14.13......Page 454
Problem 14.17......Page 455
Problem 14.19......Page 456
Problem 14.23......Page 457
Problem 14.25......Page 458
Problem 14.29......Page 459
15.1 Counting One Thing by Counting Another......Page 461
15.2 Counting Sequences......Page 462
15.3 The Generalized Product Rule......Page 465
15.4 The Division Rule......Page 469
15.5 Counting Subsets......Page 472
15.6 Sequences with Repetitions......Page 473
15.7 The Binomial Theorem......Page 475
15.9 Counting Practice: Poker Hands......Page 477
15.10 Inclusion-Exclusion......Page 482
15.11 Combinatorial Proofs......Page 488
15.12 The Pigeonhole Principle......Page 491
15.13 A Magic Trick......Page 496
Problem 15.2......Page 501
Problem 15.4......Page 502
Problem 15.5......Page 503
Problem 15.8......Page 504
Problem 15.11......Page 505
Problem 15.13......Page 506
Problem 15.15......Page 507
Problem 15.16......Page 508
Problem 15.20......Page 509
Problem 15.21......Page 510
Problem 15.22......Page 511
Problem 15.24......Page 512
Problem 15.25......Page 513
Problem 15.28......Page 514
Problem 15.29......Page 515
Problem 15.31......Page 516
Problem 15.32......Page 517
Problem 15.33......Page 518
Problem 15.36......Page 519
Problem 15.38......Page 520
Problem 15.40......Page 521
Problem 15.43......Page 522
Problem 15.46......Page 523
IV Probability......Page 525
16.1 Let's Make a Deal......Page 529
16.2 The Four Step Method......Page 530
16.3 Strange Dice......Page 539
16.4 Set Theory and Probability......Page 547
16.5 Conditional Probability......Page 551
16.6 Independence......Page 563
16.7 The Birthday Principle......Page 569
Problem 16.2......Page 572
Problem 16.3......Page 573
Problem 16.4......Page 574
Problem 16.6......Page 575
Problem 16.7......Page 576
Problem 16.9......Page 577
Problem 16.11......Page 578
Problem 16.13......Page 579
Problem 16.14......Page 580
Problem 16.16......Page 581
Problem 16.18......Page 582
Problem 16.20......Page 583
Problem 16.23......Page 584
Problem 16.24......Page 585
Problem 16.26......Page 586
Problem 16.27......Page 587
17.1 Random Variable Examples......Page 589
17.2 Independence......Page 591
17.3 Distribution Functions......Page 592
17.4 Great Expectations......Page 600
17.5 Linearity of Expectation......Page 612
Problem 17.2......Page 620
Problem 17.3......Page 621
Problem 17.5......Page 622
Problem 17.7......Page 623
Problem 17.8......Page 624
Problem 17.9......Page 625
Problem 17.11......Page 626
Problem 17.12......Page 627
Problem 17.14......Page 628
Problem 17.15......Page 629
Problem 17.16......Page 630
Problem 17.18......Page 631
18.1 Why the Mean?......Page 633
18.2 Markov's Theorem......Page 634
18.3 Chebyshev's Theorem......Page 636
18.4 Properties of Variance......Page 640
18.5 Estimation by Random Sampling......Page 644
18.6 Confidence versus Probability......Page 649
18.7 Sums of Random Variables......Page 650
18.8 Really Great Expectations......Page 660
Problem 18.2......Page 664
Problem 18.4......Page 665
Problem 18.6......Page 666
Problem 18.9......Page 667
Problem 18.10......Page 668
Problem 18.12......Page 669
Problem 18.14......Page 670
Problem 18.15......Page 671
Problem 18.17......Page 672
Problem 18.18......Page 673
Problem 18.19......Page 674
Problem 18.21......Page 675
Problem 18.23......Page 676
Problem 18.24......Page 677
19.1 Gamblers' Ruin......Page 679
19.2 Random Walks on Graphs......Page 685
Problem 19.1......Page 690
Problem 19.3......Page 691
Problem 19.4......Page 693
Problem 19.7......Page 694
Index......Page 697