Tabs for Contents, notes, highlights

Hide Contents, Notes, and Highlights

Search TermsShow Hide

« Back to eTextbook

Copyright, iv
Preface, xi
Acknowledgments, xvii
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
Appendix A. Matrices, 627
Appendix B. Algebra Review, 631
Appendix C. Pseudocode, 644
References, 650
Hints and Solutions to Selected Exercises, 655
Index, 754
List of Symbols, IFC-1
List of Symbols, IBC-1

Search Results

« Back to eTextbook


PAGE	Description

115	...

Tabs for Contents, notes, highlights

Table of Contents

Search Results