1 Sets and Logic 1
1.1 Sets 2
1.2 Propositions 14
1.3 Conditional Propositions and Logical Equivalence 21
1.4 Arguments and Rules of Inference 31
1.5 Quantifiers 36
1.6 Nested Quantifiers 51
Problem-Solving Corner:Quantifiers 60
Notes 62
Chapter Review 62
Chapter Self-Test 63
Computer Exercises 64
2 Proofs 66
2.1 Mathematical Systems,Direct Proofs,and Counterexamples 67
2.2 More Methods of Proof 76
Problem-Solving Corner:Proving Some Properties of Real Numbers 87
2.3 Resolution Proofs 90
2.4 Mathematical Induction 93
Problem-Solving Corner:Mathematical Induction 106
2.5 Strong Form of Induction and the Well-Ordering Property 108
Notes 115
Chapter Review 115
Chapter Self-Test 116
Computer Exercises 116
3 Functions,Sequences,and Relations 117
3.1 Functions 117
Problem-Solving Corner:Functions 135
3.2 Sequences and Strings 136
3.3 Relations 148
3.4 Equivalence Relations 159
Problem-Solving Corner:Equivalence Relations 166
3.5 Matrices of Relations 168
3.6 Relational Databases 173
Notes 178
Chapter Review 178
Chapter Self-Test 179
Computer Exercises 180
4 Algorithms 181
4.1 Introduction 181
4.2 Examples of Algorithms 186
4.3 Analysis of Algorithms 193
Problem-Solving Corner:Design and Analysis of an Algorithm 211
4.4 Recursive Algorithms 213
Notes 220
Chapter Review 221
Chapter Self-Test 221
Computer Exercises 222
5 Introduction to Number Theory 223
5.1 Divisors 223
5.2 Representations of Integers and Integer Algorithms 234
5.3 The Euclidean Algorithm 248
Problem-Solving Corner:Making Postage 259
5.4 The RSA Public-Key Cryptosystem 260
Notes 263
Chapter Review 263
Chapter Self-Test 263
Computer Exercises 264
6 Counting Methods and the Pigeonhole Principle 265
6.1 Basic Principles 265
Problem-Solving Corner:Counting 277
6.2 Permutations and Combinations 278
Problem-Solving Corner:Combinations 291
6.3 Generalized Permutations and Combinations 293
6.4 Algorithms for Generating Permutations and Combinations 299
6.5 Introduction to Discrete Probability 305
6.6 Discrete Probability Theory 309
6.7 Binomial Coefficients and Combinatorial Identities 320
6.8 The Pigeonhole Principle 325
Notes 330
Chapter Review 330
Chapter Self-Test 330
Computer Exercises 332
7 Recurrence Relations 333
7.1 Introduction 333
7.2 Solving Recurrence Relations 345
Problem-Solving Corner:Recurrence Relations 358
7.3 Applications to the Analysis of Algorithms 361
Notes 373
Chapter Review 373
Chapter Self-Test 374
Computer Exercises 374
8 Graph Theory 376
8.1 Introduction 377
8.2 Paths and Cycles 388
Problem-Solving Corner:Graphs 399
8.3 Hamiltonian Cycles and the Traveling Salesperson Problem 400
8.4 A Shortest-Path Algorithm 407
8.5 Representations of Graphs 412
8.6 Isomorphisms of Graphs 417
8.7 Planar Graphs 425
8.8 Instant Insanity 431
Notes 435
Chapter Review 436
Chapter Self-Test 437
Computer Exercises 438
9 Trees 440
9.1 Introduction 440
9.2 Terminology and Characterizations of Trees 448
Problem-Solving Corner:Trees 453
9.3 Spanning Trees 454
9.4 Minimal Spanning Trees 461
9.5 Binary Trees 467
9.6 Tree Traversals 474
9.7 Decision Trees and the Minimum Time for Sorting 480
9.8 Isomorphisms of Trees 486
9.9 Game Trees 496
Notes 505
Chapter Review 505
Chapter Self-Test 506
Computer Exercises 508
10 Network Models 510
10.1 Introduction 510
10.2 A Maximal Flow Algorithm 516
10.3 The Max Flow,Min Cut Theorem 524
10.4 Matching 528
Problem-Solving Corner:Matching 533
Notes 534
Chapter Review 535
Chapter Self-Test 536
Computer Exercises 536
11 Boolean Algebras and Combinatorial Circuits 537
11.1 Combinatorial Circuits 537
11.2 Properties of Combinatorial Circuits 544
11.3 Boolean Algebras 549
Problem-Solving Corner:Boolean Algebras 554
11.4 Boolean Functions and Synthesis of Circuits 556
11.5 Applications 561
Notes 570
Chapter Review 570
Chapter Self-Test 571
Computer Exercises 572
12 Automata,Grammars,and Languages 573
12.1 Sequential Circuits and Finite-State Machines 573
12.2 Finite-State Automata 579
12.3 Languages and Grammars 585
12.4 Nondeterministic Finite-State Automata 595
12.5 Relationships Between Languages and Automata 602
Notes 608
Chapter Review 609
Chapter Self-Test 609
Computer Exercises 611
13 Computational Geometry 612
13.1 The Closest-Pair Problem 612
13.2 An Algorithm to Compute the Convex Hull 617
Notes 625
Chapter Review 625
Chapter Self-Test 625
Computer Exercises 626
Appendix 627
A Matrices 627
B Algebra Review 631
C Pseudocode 644
References 650
Hints and Solutions to Selected Exercises 655
Index 754