Solutions Manual for Discrete Mathematics (Classic Version), 5th Edition by John A. Dossey – Complete Chapters 1–13

INSTRUCTOR’S
SOLUTIONS MANUAL


DISCRETE MATHEMATICS
FIFTH EDITION

John A. Dossey
@




Illinois State University
Te




Albert D. Otto
Illinois State University
st




Lawrence E. Spence
Illinois State University
ba




Charles Vanden Eynden
Illinois State University
nk
sm
af
ia




@Testbanksmafia

, Contents


1 An Introduction to Combinatorial Problems and Techniques 1

1.1 The Time to Complete a Project . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 A Matching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 A Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
@



1.4 Algorithms and Their Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . 4
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
Te



2 Sets, Relations, and Functions 6

2.1 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Partial Ordering Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
st



2.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
ba



Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12


3 Coding Theory 14
nk



3.1 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 The RSA Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 Error-Detecting and Error-Correcting Codes . . . . . . . . . . . . . . . . . . 17
sm



3.5 Matrix Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6 Matrix Codes That Correct All Single-Digit Errors . . . . . . . . . . . . . . . 19
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20


iii
af
ia




@Testbanksmafia

, Table of Contents


4 Graphs 22

4.1 Graphs and Their Representations . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Paths and Circuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.3 Shortest Paths and Distance . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4 Coloring a Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.5 Directed Graphs and Multigraphs . . . . . . . . . . . . . . . . . . . . . . . . 30
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34


5 Trees 36

5.1 Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.3 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.4 Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.5 Binary Trees and Traversals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.6 Optimal Binary Trees and Binary Search Trees . . . . . . . . . . . . . . . . . 51
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
@




6 Matching 63
Te



6.1 Systems of Distinct Representatives . . . . . . . . . . . . . . . . . . . . . . . 63
6.2 Matchings in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.3 A Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.4 Applications of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.5 The Hungarian Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
st



Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67


7 Network Flows 68
ba




7.1 Flows and Cuts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.2 A Flow Augmentation Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.3 The Max-Flow Min-Cut Theorem . . . . . . . . . . . . . . . . . . . . . . . . 73
7.4 Flows and Matchings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
nk



Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
sm




iv
af
ia




@Testbanksmafia

, Table of Contents


8 Counting Techniques 78

8.1 Pascal’s Triangle and the Binomial Theorem . . . . . . . . . . . . . . . . . . 78
8.2 Three Fundamental Principles . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.3 Permutations and Combinations . . . . . . . . . . . . . . . . . . . . . . . . . 79
8.4 Arrangements and Selections with Repetitions . . . . . . . . . . . . . . . . . 79
8.5 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.6 The Principle of Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . 81
8.7 Generating Permutations and r-Combinations . . . . . . . . . . . . . . . . . 82
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82




9 Recurrence Relations and Generating Functions 84
@




9.1 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
9.2 The Method of Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.3 Linear Difference Equations with Constant Coefficients . . . . . . . . . . . . 91
9.4∗
Te



Analyzing the Efficiency of Algorithms with Recurrence Relations . . . . . . 94
9.5 Counting with Generating Functions . . . . . . . . . . . . . . . . . . . . . . . 99
9.6 The Algebra of Generating Functions . . . . . . . . . . . . . . . . . . . . . . 100
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
st
ba




10 Combinatorial Circuits and Finite State Machines 105
nk




10.1 Logical Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
10.2 Creating Combinatorial Circuits . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.3 Karnaugh Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10.4 Finite State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
sm



Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115



v
af
ia




@Testbanksmafia