Exam (elaborations)
Solutions Manual for Discrete Mathematics (Classic Version) 5th Edition by John A. Dossey
Course
Discrete Mathematics
Institution
Discrete Mathematics
Discrete Mathematics (Classic Version) 5th Edition John A. Dossey SOLUTION
[Show more]
Preview 4 out of 135 pages
Uploaded on
October 24, 2024
Number of pages
135
Written in
2024/2025
Type
Exam (elaborations)
Contains
Questions & answers
Institution
Discrete Mathematics
Course
Discrete Mathematics
$19.99
100% satisfaction guarantee
Immediately available after payment
Both online and in PDF
No strings attached
INSTRUCTOR’S
SOLUTIONS MANUAL
R
U
DISCRETE MATHEMATICS
SE
FIFTH EDITION
John A. Dossey IS
O
Illinois State University
N
Albert D. Otto
N
Illinois State University
O
Lawrence E. Spence
C
Illinois State University
ED
Charles Vanden Eynden
Illinois State University
M
, Contents
R
U
SE
1 An Introduction to Combinatorial Problems and Techniques 1
IS
1.1 The Time to Complete a Project . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 A Matching Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 A Knapsack Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
O
1.4 Algorithms and Their Efficiency . . . . . . . . . . . . . . . . . . . . . . . . . 4
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
N
2 Sets, Relations, and Functions 6
N
2.1 Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
O
2.3 Partial Ordering Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5 Mathematical Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
C
2.6 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
ED
3 Coding Theory 14
3.1 Congruence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
M
3.2 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 The RSA Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4 Error-Detecting and Error-Correcting Codes . . . . . . . . . . . . . . . . . . 17
3.5 Matrix Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.6 Matrix Codes That Correct All Single-Digit Errors . . . . . . . . . . . . . . . 19
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
iii
,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
R
4.5 Directed Graphs and Multigraphs . . . . . . . . . . . . . . . . . . . . . . . . 30
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
U
5 Trees 36
SE
5.1 Properties of Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
5.2 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
5.3 Depth-First Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
5.4 Rooted Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
5.5
5.6
Binary Trees and Traversals . . . . . . . . . . .
Optimal Binary Trees and Binary Search Trees
Supplementary Exercises . . . . . . . . . . . . IS .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
46
51
60
O
6 Matching 63
N
6.1 Systems of Distinct Representatives . . . . . . . . . . . . . . . . . . . . . . . 63
6.2 Matchings in Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
N
6.3 A Matching Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
6.4 Applications of the Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 66
O
6.5 The Hungarian Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
C
7 Network Flows 68
ED
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
M
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
iv
, 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
R
8.5 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.6 The Principle of Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . 81
Generating Permutations and r-Combinations
U
8.7 . . . . . . . . . . . . . . . . . 82
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
SE
9 Recurrence Relations and Generating Functions IS 84
O
9.1 Recurrence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
9.2 The Method of Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
N
9.3 Linear Difference Equations with Constant Coefficients . . . . . . . . . . . . 91
9.4∗ Analyzing the Efficiency of Algorithms with Recurrence Relations . . . . . . 94
N
9.5 Counting with Generating Functions . . . . . . . . . . . . . . . . . . . . . . . 99
9.6 The Algebra of Generating Functions . . . . . . . . . . . . . . . . . . . . . . 100
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
O
C
ED
10 Combinatorial Circuits and Finite State Machines 105
M
10.1 Logical Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
10.2 Creating Combinatorial Circuits . . . . . . . . . . . . . . . . . . . . . . . . . 107
10.3 Karnaugh Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
10.4 Finite State Machines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
Supplementary Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
v