Discrete Mathematics for Computer Science

Cover......Page 1
Index of Notation......Page 2
Title Page......Page 6
Copyright Page......Page 7
Contents......Page 8
Preface......Page 20
1.1 Basic Definitions......Page 25
1.1.1 Describing Sets Mathematically......Page 26
1.1.3 Equality of Sets......Page 28
1.1.5 Relations Between Sets......Page 29
1.1.6 Venn Diagrams......Page 31
1.1.7 Templates......Page 32
1.2 Exercises......Page 37
1.3.1 Union and Intersection......Page 39
1.3.2 Set Difference, Complements, and DeMorgan\'s Laws......Page 44
1.3.3 New Proof Templates......Page 50
1.3.5 Lattices and Boolean Algebras......Page 52
1.4 Exercises......Page 55
1.5.1 Finite Cardinality......Page 58
1.5.2 Principle of Inclusion-Exclusion for Two Sets......Page 60
1.5.3 Principle of Inclusion-Exclusion for Three Sets......Page 61
1.5.4 Principle of Inclusion-Exclusion for Finitely Many Sets......Page 65
1.6 Exercises......Page 66
1.71 A First Form of Induction......Page 69
1.72 A Template for Constructing Proofs by Induction......Page 73
1.73 Application: Fibonacci Numbers......Page 75
1.74 Application: Size of a Power Set......Page 77
1.75 Application: Geometric Series......Page 78
1.8.1 Pseudocode Conventions......Page 80
1.8.3 Two Algorithms for Computing Square Roots......Page 82
1.9 Exercises......Page 86
1.10 Strong Form of Mathematical Induction......Page 90
1.10.1 Using the Strong Form of Mathematical Induction......Page 93
1.10.2 Application: Algorithm to Compute Powers......Page 96
1.10.3 Application: Finding Factorizations......Page 99
1.10.4 Application: Binary Search......Page 101
1.11 Exercises......Page 103
1.12 Chapter Review......Page 105
1.12.1 Summary......Page 106
1.12.2 Starting to Review......Page 108
1.12.3 Review Questions......Page 109
1.12.4 Using Discrete Mathematics in Computer Science......Page 111
2.1 Introduction to Propositional Logic......Page 113
2.1.1 Formulas......Page 116
2.1.2 Expression Trees for Formulas......Page 118
2.1.3 Abbreviated Notation for Formulas......Page 121
2.1.4 Using Gates to Represent Formulas......Page 122
2.2 Exercises......Page 123
2.3 Truth and Logical Truth......Page 126
2.3.1 Tautologies......Page 130
2.3.3 Logically Valid Inferences......Page 133
2.3.4 Combinatorial Networks......Page 136
2.3.5 Substituting Equivalent Subformulas......Page 138
2.3.6 Simplifying Negations......Page 139
2.4 Exercises......Page 140
2.5 Normal Forms......Page 145
2.5.1 Disjunctive Normal Form......Page 146
2.5.2 Application: DNF and Combinatorial Networks......Page 148
2.5.3 Conjunctive Normal Form......Page 149
2.5.5 Testing Satisfiability and Validity......Page 151
2.5.7 Resolution Proofs: Automating Logic......Page 153
2.6 Exercises......Page 155
2.7 Predicates and Quantification......Page 158
2.72 Quantification......Page 159
2.73 Restricted Quantification......Page 160
2.74 Nested Quantifiers......Page 161
2.75 Negation and Quantification......Page 162
2.76 Quantification with Conjunction and Disjunction......Page 163
2.77 Application: Loop Invariant Assertions......Page 165
2.8 Exercises......Page 167
2.9 Chapter Review......Page 171
2.9.1 Summary......Page 172
2.9.2 Starting to Review......Page 173
2.9.3 Review Questions......Page 174
2.9.4 Using Discrete Mathematics in Computer Science......Page 175
3.1 Binary Relations......Page 181
3.1.1 n-ary Relations......Page 186
3.2.1 Inverses......Page 187
3.2.2 Composition......Page 189
3.3 Exercises......Page 190
3.4 Special Types of Relations......Page 191
3.4.1 Reflexive and Irreflexive Relations......Page 192
3.4.2 Symmetric and Antisymmetric Relations......Page 193
3.4.3 Transitive Relations......Page 196
3.4.4 Reflexive, Symmetric, and Transitive Closures......Page 197
3.4.5 Application: Transitive Closures in Medicine and Engineering......Page 200
3.5 Exercises......Page 202
3.6 Equivalence Relations......Page 205
3.6.1 Partitions......Page 207
3.6.2 Comparing Equivalence Relations......Page 210
3.7 Exercises......Page 212
3.8.1 Partial Orderings......Page 215
3.8.2 Linear Orderings......Page 218
3.8.4 Optimal Elements in Orderings......Page 220
3.8.5 Application: Finding a Minimal Element......Page 222
3.8.6 Application: Embedding a Partial Order......Page 224
3.9 Exercises......Page 225
3.10 Relational Databases: An Introduction......Page 226
3.10.1 Storing Information in Relations......Page 227
3.10.2 Relational Algebra......Page 228
3.11 Exercises......Page 235
3.12 Chapter Review......Page 236
3.12.1 Summary......Page 237
3.12.2 Starting to Review......Page 239
3.12.3 Review Questions......Page 240
3.12.4 Using Discrete Mathematics in Computer Science......Page 241
4.1 Basic Definitions......Page 243
4.1.1 Functions as Rules......Page 245
4.1.2 Functions as Sets......Page 246
4.1.3 Recursively Defined Functions......Page 248
4.1.4 Graphs of Functions......Page 249
4.1.5 Equality of Functions......Page 250
4.1.6 Restrictions of Functions......Page 252
4.1.7 Partial Functions......Page 253
4.1.8 1-1 and Onto Functions......Page 255
4.1.9 Increasing and Decreasing Functions......Page 261
4.2 Exercises......Page 263
4.3.1 Composition of Functions......Page 267
4.3.2 Inverses of Functions......Page 269
4.4 Sequences and Subsequences......Page 272
4.5 Exercises......Page 275
4.6 The Pigeon-Hole Principle......Page 277
4.6.1 k to 1 Functions......Page 278
4.6.2 Proofs of the Pigeon-Hole Principle......Page 279
4.6.3 Application: Decimal Expansion of Rational Numbers......Page 281
4.6.4 Application: Problems with Divisors and Schedules......Page 283
4.6.5 Application: Two Combinatorial Results......Page 284
4.7 Exercises......Page 286
4.8 Countable and Uncountable Sets......Page 288
4.8.1 Countably Infinite Sets......Page 290
4.8.2 Cantor\'s First Diagonal Argument......Page 292
4.8.3 Uncountable Sets and Cantor\'s Second Diagonal Argument......Page 294
4.9 Exercises......Page 297
4.10.1 Summary......Page 299
4.10.2 Starting to Review......Page 301
4.10.3 Review Questions......Page 303
4.10.4 Using Discrete Mathematics in Computer Science......Page 304
CHAPTER 5 Analysis of Algorithms......Page 307
5.1.1 A Measure for Comparing Growth Rates......Page 308
5.1.2 Properties of Asymptotic Domination......Page 313
5.1.3 Polynomial Functions......Page 315
5.1.4 Exponential and Logarithmic Functions......Page 317
5.2 Exercises......Page 320
5.3 Complexity of Programs......Page 322
5.3.1 Counting Statements......Page 324
5.3.2 Two Algorithms Illustrating Selection......Page 326
5.3.3 An Algorithm Illustrating Repetition......Page 328
5.3.4 An Algorithm Illustrating Nested Repetition......Page 331
5.3.5 Time Complexity of an Algorithm......Page 332
5.3.6 Variants on the Definition of Complexity......Page 335
5.4 Exercises......Page 337
5.5 Uncomputability......Page 340
5.5.1 The Halting Problem......Page 342
5.6.1 Summary......Page 345
5.6.3 Review Questions......Page 346
5.6.4 Using Discrete Mathematics in Computer Science......Page 347
6.1 Introduction to Graph Theory......Page 355
6.1.1 Definitions......Page 358
6.1.2 Subgraphs......Page 360
6.2 The Handshaking Problem......Page 362
6.3 Paths and Cycles......Page 364
6.3.1 Hamiltonian Cycles......Page 365
6.4 Graph Isomorphism......Page 369
6.5.1 Adjacency Matrix......Page 370
6.5.2 Adjacency Lists......Page 371
6.6 Exercises......Page 372
6.71 The Relation CONN......Page 376
6.7.2 Depth First Search......Page 378
6.74 Breadth First Search......Page 381
6.7.5 Finding Connected Components......Page 383
6.8 The K6nigsberg Bridge Problem......Page 385
6.8.1 Graph Tracing......Page 389
6.9 Exercises......Page 391
6.10 Trees......Page 394
6.10.1 Definition of Trees......Page 395
6.10.2 Characterization of Trees......Page 396
6.11.1 Kruskal\'s Algorithm......Page 398
6.11.2 Correctness of Kruskal\'s Algorithm......Page 399
6.11.3 Kruskal\'s Algorithm for Weighted Graphs......Page 400
6.12 Rooted Trees......Page 402
6.12.1 Binary Trees......Page 404
6.12.2 Binary Search Trees......Page 406
6.12.3 Tree Traversals......Page 409
6.12.4 Application: Decision Trees......Page 411
6.13 Exercises......Page 413
6.14 Directed Graphs......Page 416
6.14.1 Basic Definitions......Page 417
6.15 Application: Scheduling a Meeting Facility......Page 418
6.15.1 WAITFOR Graphs......Page 420
6.16.1 Directed Cycle Detection Algorithm......Page 421
6.16.2 Correctness of Directed Cycle Detection......Page 422
6.17 Priority in Scheduling......Page 423
6.171 Algorithm for Topological Sort......Page 424
6.172 Correctness of Topological Sort Algorithm......Page 425
6.18.1 Strongly Connected Directed Graphs......Page 426
6.18.2 Application: Designing One-Way Street Grids......Page 428
6.19 Eulerian Circuits in Directed Graphs......Page 429
6.20 Exercises......Page 430
6.21.1 Summary......Page 433
6.21.2 Starting to Review......Page 435
6.21.3 Review Questions......Page 437
6.21.4 Using Discrete Mathematics in Computer Science......Page 440
7.1 Traveling Salesperson\'s Problem......Page 445
7.2 Counting Principles......Page 447
7.2.1 The Multiplication Principle......Page 448
7.2.2 Addition Principle......Page 450
7.3 Set Decomposition Principle......Page 452
7.3.1 Counting the Complement......Page 453
7.3.2 Using the Pigeon-Hole Principle......Page 454
7.3.3 Application: UNIX Logon Passwords......Page 456
7.4 Exercises......Page 457
7.5.1 Permutations......Page 460
7.5.2 Linear Arrangements......Page 461
7.5.3 Circular Permutations......Page 463
7.5.4 Combinations......Page 464
7.5.5 Poker Hands......Page 465
7.5.6 Counting the Complement......Page 467
7.5.7 Decomposition into Subproblems......Page 468
7.6 Constructing the kth Permutation......Page 470
7.7 Exercises......Page 472
7.8 Counting with Repeated Objects......Page 475
7.8.1 Permutations with Repetitions......Page 476
78.2 Combinations with Repetitions......Page 479
7.9 Combinatorial Identities......Page 481
7.9.1 Binomial Coefficients......Page 483
7.9.2 Multinomials......Page 486
7.10 Pascal\'s Triangle......Page 487
7.11 Exercises......Page 489
7.12 Chapter Review......Page 493
7.12.1 Summary......Page 494
712.3 Review Questions......Page 495
7.12.4 Using Discrete Mathematics in Computer Science......Page 496
8.1 Ideas of Chance in Computer Science......Page 499
8.1.1 Introductory Examples......Page 500
8.1.2 Basic Definitions......Page 502
8.1.4 Introductory Example Reconsidered......Page 504
8.1.5 The Combinatorics of Uniform Probability Density......Page 506
8.1.6 Set Theory and the Probability of Events......Page 508
8.2 Exercises......Page 512
8.3 Cross Product Sample Spaces......Page 515
8.3.1 A Multiplication Principle......Page 516
8.3.2 The Cross Product of Sample Spaces......Page 519
8.3.3 Bernoulli Trial Processes......Page 522
8.3.4 Events of Cross Product Form......Page 524
8.3.5 Two Ways of Viewing Events......Page 526
8.4 Exercises......Page 529
8.5.1 Independent Events......Page 531
8.5.2 Introduction to Conditional Probability......Page 533
8.5.3 Exploring Conditional Probability......Page 536
8.5.4 Using Bayes\' Rule with the Theorem of Total Probability......Page 538
8.6 Exercises......Page 541
8.7.1 Distributions of a Random Variable......Page 544
8.7.3 The Hypergeometric Distribution......Page 546
8.7.4 Expectation of a Random Variable......Page 548
8.7.5 The Sum of Random Variables......Page 550
8.8 Exercises......Page 553
8.9 Variance, Standard Deviation, and the Law of Averages......Page 554
8.9.1 Variance and Standard Deviation......Page 555
8.9.2 Independent Random Variables......Page 557
8.10 Exercises......Page 563
8.11 Chapter Review......Page 564
8.11.1 Summary......Page 565
8.11.2 Starting to Review......Page 566
8.11.3 Review Questions......Page 567
8.11.4 Using Discrete Mathematics in Computer Science......Page 569
9.1 The Tower of Hanoi Problem......Page 573
9.1.2 Solving the Tower of Hanoi Recurrence......Page 576
9.2 Solving First-Order Recurrence Relations......Page 578
9.2.1 Solving First-Order Recurrences Using Back Substitution......Page 579
9.3 Exercises......Page 582
9.4 Fibonacci Recurrence Relation......Page 585
9.4.1 Second Order-Recurrence Relations......Page 586
9.4.2 Solving the Fibonacci Recurrence......Page 588
9.4.3 Rules for Solving Second-Order Recurrence Relations......Page 590
9.5 Exercises......Page 591
9.7 Binary Search......Page 592
9.71 Correctness......Page 593
9.72 Complexity......Page 594
9.8.1 Correctness......Page 595
9.8.3 Complexity......Page 596
9.9 Multiplication of n-Bit Numbers......Page 597
9.10 Divide-and-Conquer Recurrence Relations......Page 600
9.11 Exercises......Page 603
9.12 Chapter Review......Page 604
9.12.1 Summary......Page 605
9.12.3 Review Questions......Page 606
9.12.4 Using Discrete Mathematics in Computer Science......Page 607
Appendix A......Page 611
Appendix B......Page 615
Index......Page 619
Index of Notation (continued)......Page 625
Back Cover......Page 627