Student's Solutions Guide to accompany Discrete Mathematics and Its Applications

by Rosen, Kenneth

• ISBN13: 9780073107790
• ISBN10: 0073107794
• Edition: 6th
• Format: Paperback
• Copyright: 2006-07-27
• Publisher: McGraw-Hill Science/Engineering/Math

Table of Contents

Preface	iii
The Foundations: Logic and Proofs	1	(46)
Propositional Logic	1	(9)
Propositional Equivalences	10	(5)
Predicates and Quantifiers	15	(6)
Nested Quantifiers	21	(9)
Rules of Inference	30	(4)
Introduction to Proofs	34	(4)
Proof Methods and Strategy	38	(9)
Guide to Review Questions for Chapter 1	42	(1)
Supplementary Exercises for Chapter 1	43	(2)
Writing Projects for Chapter 1	45	(2)
Basic Structures: Sets, Functions, Sequences, and Sums	47	(25)
Sets	47	(3)
Set Operations	50	(5)
Functions	55	(8)
Sequences and Summations	63	(9)
Guide to Review Questions for Chapter 2	68	(1)
Supplementary Exercises for Chapter 2	69	(2)
Writing Projects for Chapter 2	71	(1)
The Fundamentals: Algorithms, the Integers, and Matrices	72	(48)
Algorithms	72	(9)
The Growth of Functions	81	(5)
Complexity of Algorithms	86	(3)
The Integers and Division	89	(2)
Primes and Greatest Common Divisors	91	(4)
Integers and Algorithms	95	(5)
Applications of Number Theory	100	(8)
Matrices	108	(12)
Guide to Review Questions for Chapter 3	112	(1)
Supplementary Exercises for Chapter 3	113	(5)
Writing Projects for Chapter 3	118	(2)
Induction and Recursion	120	(47)
Mathematical Induction	120	(12)
Strong Induction and Well-Ordering	132	(6)
Recursive Definitions and Structural Induction	138	(9)
Recursive Algorithms	147	(5)
Program Correctness	152	(15)
Guide to Review Questions for Chapter 4	154	(2)
Supplementary Exercises for Chapter 4	156	(10)
Writing Projects for Chapter 4	166	(1)
Counting	167	(39)
The Basics of Counting	167	(8)
The Pigeonhole Principle	175	(5)
Permutations and Combinations	180	(4)
Binomial Coefficients	184	(5)
Generalized Permutations and Combinations	189	(7)
Generating Permutations and Combinations	196	(10)
Guide to Review Questions for Chapter 5	198	(1)
Supplementary Exercises for Chapter 5	199	(6)
Writing Projects for Chapter 5	205	(1)
Discrete Probability	206	(22)
An Introduction to Discrete Probability	206	(3)
Probability Theory	209	(6)
Bayes' Theorem	215	(2)
Expected Value and Variance	217	(11)
Guide to Review Questions for Chapter 6	222	(1)
Supplementary Exercises for Chapter 6	223	(4)
Writing Projects for Chapter 6	227	(1)
Advanced Counting Techniques	228	(52)
Recurrence Relations	228	(13)
Solving Linear Recurrence Relations	241	(10)
Divide-and-Conquer Algorithms and Recurrence Relations	251	(4)
Generating Functions	255	(12)
Inclusion-Exclusion	267	(2)
Applications of Inclusion--Exclusion	269	(11)
Guide to Review Questions for Chapter 7	273	(1)
Supplementary Exercises for Chapter 7	274	(5)
Writing Projects for Chapter 7	279	(1)
Relations	280	(40)
Relations and Their Properties	280	(8)
n-ary Relations and Their Applications	288	(2)
Representing Relations	290	(3)
Closures of Relations	293	(4)
Equivalence Relations	297	(8)
Partial Orderings	305	(15)
Guide to Review Questions for Chapter 8	313	(1)
Supplementary Exercises for Chapter 8	314	(5)
Writing Projects for Chapter 8	319	(1)
Graphs	320	(47)
Graphs and Graph Models	320	(3)
Graph Terminology and Special Types of Graphs	323	(6)
Representing Graphs and Graph Isomorphism	329	(7)
Connectivity	336	(6)
Euler and Hamilton Paths	342	(5)
Shortest-Path Problems	347	(4)
Planar Graphs	351	(4)
Graph Coloring	355	(12)
Guide to Review Questions for Chapter 9	359	(1)
Supplementary Exercises for Chapter 9	360	(5)
Writing Projects for Chapter 9	365	(2)
Trees	367	(32)
Introduction to Trees	367	(5)
Applications of Trees	372	(9)
Tree Traversal	381	(4)
Spanning Trees	385	(5)
Minimum Spanning Trees	390	(9)
Guide to Review Questions for Chapter 10	393	(1)
Supplementary Exercises for Chapter 10	394	(3)
Writing Projects for Chapter 10	397	(2)
Boolean Algebra	399	(21)
Boolean Functions	399	(4)
Representing Boolean Functions	403	(2)
Logic Gates	405	(3)
Minimization of Circuits	408	(12)
Guide to Review Questions for Chapter 11	416	(1)
Supplementary Exercises for Chapter 11	417	(2)
Writing Projects for Chapter 11	419	(1)
Modeling Computation	420	(32)
Languages and Grammars	420	(7)
Finite-State Machines with Output	427	(5)
Finite-State Machines with No Output	432	(5)
Language Recognition	437	(4)
Turing Machines	441	(11)
Guide to Review Questions for Chapter 12	445	(1)
Supplementary Exercises for Chapter 12	446	(4)
Writing Projects for Chapter 12	450	(2)
APPENDIXES	452	(3)
Appendix 1 Axioms for the Real Numbers and the Positive Integers	452	(2)
Appendix 2 Exponential and Logarithmic Functions	454	(1)
Appendix 3 Pseudocode	454	(1)
A Guide to Proof-Writing	455	(11)
References and Advice on Writing Projects	466	(8)
Sample Chapter Tests with Solutions	474	(28)
Common Mistakes in Discrete Mathematics	502	(10)
Solving Problems in Discrete Mathematics	502	(1)
List of Common Mistakes	503	(9)
Crib Sheets	512