All Chapters Covered
SOLUTION MANUAL
, Contents
Preface iii
CHAPTER 1 The Foundations: Logic and Proofs 1
1.1 Propositional Logic 1
1.2 Applications of Propositional Logic 8
1.3 Propositional Equivalences 11
1.4 Predicates and Quantifiers 17
1.5 Nested Quantifiers 23
1.6 Rules of Inference 32
1. 7 Introduction to Proofs 36
1.8 Proof Methods and Strategy 40
Guide to Review Questions for Chapter 1 44
Supplementary Exercises for Chapter 1 45
Writing Projects for Chapter 1 48
CHAPTER 2 Basic Structures: Sets, Functions,
Sequences, Sums, and Matrices 50
2.1 Sets 50
2.2 Set Operations 53
2 .3 Functions 59
2.4 Sequences and Summations 68
2.5 Cardinality of Sets 75
2.6 Matrices 79
Guide to Review Questions for Chapter 2 83
Supplementary Exercises for Chapter 2 84
Writing Projects for Chapter 2 87
CHAPTER 3 Algorithms 88
3.1 Algorithms 88
3.2 The Growth of Functions 97
3.3 Complexity of Algorithms 103
Guide to Review Questions for Chapter 3 107
Supplementary Exercises for Chapter 3 108
Writing Projects for Chapter 3 112
CHAPTER 4 Number Theory and Cryptography 113
4.1 Divisibility and Modular Arithmetic 113
4.2 Integer Representations and Algorithms 116
4.3 Primes and Greatest Common Divisors 122
4.4 Solving Congruences 130
4.5 Applications of Congruences 137
4.6 Cryptography 140
Guide to Review Questions for Chapter 4 142
Supplementary Exercises for Chapter 4 143
Writing Projects for Chapter 4 147
v
,CHAPTER 5 Induction and Recursion 149
5.1 Mathematical Induction 149
5.2 Strong Induction and Well-Ordering 161
5.3 Recursive Definitions and Structural Induction 167
5.4 Recursive Algorithms 176
5.5 Program Correctness 182
Guide to Review Questions for Chapter 5 183
Supplementary Exercises for Chapter 5 185
Writing Projects for Chapter 5 195
CHAPTER 6 Counting 197
6.1 The Basics of Counting 197
6.2 The Pigeonhole Principle 206
6.3 Permutations and Combinations 211
6.4 Binomial Coefficients and Identities 216
6.5 Generalized Permutations and Combinations 220
6.6 Generating Permutations and Combinations 227
Guide to Review Questions for Chapter 6 230
Supplementary Exercises for Chapter 6 231
Writing Projects for Chapter 6 237
CHAPTER 7 Discrete Probability 239
7.1 An Introduction to Discrete Probability 239
7.2 Probability Theory 242
7.3 Bayes' Theorem 247
7.4 Expected Value and Variance 250
Guide to Review Questions for Chapter 7 255
Supplementary Exercises for Chapter 7 256
Writing Projects for Chapter 7 261
CHAPTER 8 Advanced Counting Techniques 262
8.1 Applications of Recurrence Relations 262
8.2 Solving Linear Recurrence Relations 272
8.3 Divide-and-Conquer Algorithms and Recurrence Relations 282
8.4 Generating Functions 286
8.5 Inclusion-Exclusion 298
8.6 Applications of Inclusion-Exclusion 300
Guide to Review Questions for Chapter 8 304
Supplementary Exercises for Chapter 8 305
Writing Projects for Chapter 8 310
CHAPTER 9 Relations 312
9.1 Relations and Their Properties 312
9.2 n-ary Relations and Their Applications 320
9.3 Representing Relations 322
9.4 Closures of Relations 325
Vl
, 9.5 Equivalence Relations 329
9.6 Partial Orderings 337
Guide to Review Questions for Chapter 9 345
Supplementary Exercises for Chapter 9 347
Writing Projects for Chapter 9 351
CHAPTER 10 Graphs 352
10.1 Graphs and Graph Models 352
10.2 Graph Terminology and Special Types of Graphs 355
10.3 Representing Graphs and Graph Isomorphism 361
10.4 Connectivity 368
10.5 Euler and Hamilton Paths 375
10.6 Shortest-Path Problems 381
10.7 Planar Graphs 385
10.8 Graph Coloring 389
Guide to Review Questions for Chapter 10 393
Supplementary Exercises for Chapter 10 395
Writing Projects for Chapter 10 401
CHAPTER 11 Trees 403
11.1 Introduction to Trees 403
11.2 Applications of Trees 408
11.3 Tree Traversal 417
11.4 Spanning Trees 421
11.5 Minimum Spanning Trees 427
Guide to Review Questions for Chapter 11 429
Supplementary Exercises for Chapter 11 430
Writing Projects for Chapter 11 434
CHAPTER 12 Boolean Algebra 436
12.1 Boolean Functions 436
12.2 Representing Boolean Functions 440
12.3 Logic Gates 443
12.4 Minimization of Circuits 445
Guide to Review Questions for Chapter 12 453
Supplementary Exercises for Chapter 12 454
Writing Projects for Chapter 12 456
CHAPTER 13 Modeling Computation 457
13.1 Languages and Grammars 457
13.2 Finite-State Machines with Output 464
13.3 Finite-State Machines with No Output 469
13.4 Language Recognition 474
13.5 Turing Machines 478
Guide to Review Questions for Chapter 13 482
Supplementary Exercises for Chapter 13 483
Writing Projects for Chapter 13 487
Vll
SOLUTION MANUAL
, Contents
Preface iii
CHAPTER 1 The Foundations: Logic and Proofs 1
1.1 Propositional Logic 1
1.2 Applications of Propositional Logic 8
1.3 Propositional Equivalences 11
1.4 Predicates and Quantifiers 17
1.5 Nested Quantifiers 23
1.6 Rules of Inference 32
1. 7 Introduction to Proofs 36
1.8 Proof Methods and Strategy 40
Guide to Review Questions for Chapter 1 44
Supplementary Exercises for Chapter 1 45
Writing Projects for Chapter 1 48
CHAPTER 2 Basic Structures: Sets, Functions,
Sequences, Sums, and Matrices 50
2.1 Sets 50
2.2 Set Operations 53
2 .3 Functions 59
2.4 Sequences and Summations 68
2.5 Cardinality of Sets 75
2.6 Matrices 79
Guide to Review Questions for Chapter 2 83
Supplementary Exercises for Chapter 2 84
Writing Projects for Chapter 2 87
CHAPTER 3 Algorithms 88
3.1 Algorithms 88
3.2 The Growth of Functions 97
3.3 Complexity of Algorithms 103
Guide to Review Questions for Chapter 3 107
Supplementary Exercises for Chapter 3 108
Writing Projects for Chapter 3 112
CHAPTER 4 Number Theory and Cryptography 113
4.1 Divisibility and Modular Arithmetic 113
4.2 Integer Representations and Algorithms 116
4.3 Primes and Greatest Common Divisors 122
4.4 Solving Congruences 130
4.5 Applications of Congruences 137
4.6 Cryptography 140
Guide to Review Questions for Chapter 4 142
Supplementary Exercises for Chapter 4 143
Writing Projects for Chapter 4 147
v
,CHAPTER 5 Induction and Recursion 149
5.1 Mathematical Induction 149
5.2 Strong Induction and Well-Ordering 161
5.3 Recursive Definitions and Structural Induction 167
5.4 Recursive Algorithms 176
5.5 Program Correctness 182
Guide to Review Questions for Chapter 5 183
Supplementary Exercises for Chapter 5 185
Writing Projects for Chapter 5 195
CHAPTER 6 Counting 197
6.1 The Basics of Counting 197
6.2 The Pigeonhole Principle 206
6.3 Permutations and Combinations 211
6.4 Binomial Coefficients and Identities 216
6.5 Generalized Permutations and Combinations 220
6.6 Generating Permutations and Combinations 227
Guide to Review Questions for Chapter 6 230
Supplementary Exercises for Chapter 6 231
Writing Projects for Chapter 6 237
CHAPTER 7 Discrete Probability 239
7.1 An Introduction to Discrete Probability 239
7.2 Probability Theory 242
7.3 Bayes' Theorem 247
7.4 Expected Value and Variance 250
Guide to Review Questions for Chapter 7 255
Supplementary Exercises for Chapter 7 256
Writing Projects for Chapter 7 261
CHAPTER 8 Advanced Counting Techniques 262
8.1 Applications of Recurrence Relations 262
8.2 Solving Linear Recurrence Relations 272
8.3 Divide-and-Conquer Algorithms and Recurrence Relations 282
8.4 Generating Functions 286
8.5 Inclusion-Exclusion 298
8.6 Applications of Inclusion-Exclusion 300
Guide to Review Questions for Chapter 8 304
Supplementary Exercises for Chapter 8 305
Writing Projects for Chapter 8 310
CHAPTER 9 Relations 312
9.1 Relations and Their Properties 312
9.2 n-ary Relations and Their Applications 320
9.3 Representing Relations 322
9.4 Closures of Relations 325
Vl
, 9.5 Equivalence Relations 329
9.6 Partial Orderings 337
Guide to Review Questions for Chapter 9 345
Supplementary Exercises for Chapter 9 347
Writing Projects for Chapter 9 351
CHAPTER 10 Graphs 352
10.1 Graphs and Graph Models 352
10.2 Graph Terminology and Special Types of Graphs 355
10.3 Representing Graphs and Graph Isomorphism 361
10.4 Connectivity 368
10.5 Euler and Hamilton Paths 375
10.6 Shortest-Path Problems 381
10.7 Planar Graphs 385
10.8 Graph Coloring 389
Guide to Review Questions for Chapter 10 393
Supplementary Exercises for Chapter 10 395
Writing Projects for Chapter 10 401
CHAPTER 11 Trees 403
11.1 Introduction to Trees 403
11.2 Applications of Trees 408
11.3 Tree Traversal 417
11.4 Spanning Trees 421
11.5 Minimum Spanning Trees 427
Guide to Review Questions for Chapter 11 429
Supplementary Exercises for Chapter 11 430
Writing Projects for Chapter 11 434
CHAPTER 12 Boolean Algebra 436
12.1 Boolean Functions 436
12.2 Representing Boolean Functions 440
12.3 Logic Gates 443
12.4 Minimization of Circuits 445
Guide to Review Questions for Chapter 12 453
Supplementary Exercises for Chapter 12 454
Writing Projects for Chapter 12 456
CHAPTER 13 Modeling Computation 457
13.1 Languages and Grammars 457
13.2 Finite-State Machines with Output 464
13.3 Finite-State Machines with No Output 469
13.4 Language Recognition 474
13.5 Turing Machines 478
Guide to Review Questions for Chapter 13 482
Supplementary Exercises for Chapter 13 483
Writing Projects for Chapter 13 487
Vll
