Discrete Mathematics

by Dossey, John A.; Otto, Albert D.; Spence, Lawrence E.; Vanden Eynden, Charles

• ISBN13: 9780321079121
• ISBN10: 0321079124
• Edition: 4th
• Format: Hardcover
• Copyright: 2002-01-01
• Publisher: Addison Wesley

Summary

The strong algorithmic emphasis of "Discrete Mathematics" is independent of a specific programming language, allowing students to concentrate on foundational problem-solving and analytical skills. Instructors get the topical breadth and organizational flexibility to tailor the course to the level and interests of their students. Algorithms are presented in English, eliminating the need for knowledge of a particular programming language. Computational and algorithmic exercise sets follow each chapter section and supplementary exercises and computer projects are included in the end-of-chapter material. This Fifth Edition features a new Chapter 3 covering matrix codes, error correcting codes, congruence, Euclidean algorithm and Diophantine equations, and the RSA algorithm. MARKET: Intended for use in a one-semester introductory course in discrete mathematics.

Table of Contents

To the Student	xiii
An Introduction to Combinatorial Problems and Techniques	1	(39)
The Time to Complete a Project	2	(8)
A Matching Problem	10	(6)
A Knapsack Problem	16	(7)
Algorithms and Their Efficiency	23	(17)
Historical Notes	35	(1)
Supplementary Exercises	36	(3)
Computer Projects	39	(1)
Suggested Readings	39	(1)
Sets, Relations, and Functions	40	(68)
Set Operations	40	(7)
Equivalence Relations	47	(7)
Congruence	54	(6)
Partial Ordering Relations	60	(12)
Functions	72	(12)
Mathematical Induction	84	(8)
Applications	92	(16)
Historical Notes	101	(2)
Supplementary Exercises	103	(3)
Computer Projects	106	(1)
Suggested Readings	106	(2)
Graphs	108	(76)
Graphs and Their Representations	108	(11)
Paths and Circuits	119	(17)
Shortest Paths and Distance	136	(12)
Coloring a Graph	148	(10)
Directed Graphs and Multigraphs	158	(26)
Historical Notes	175	(1)
Supplementary Exercises	176	(6)
Computer Projects	182	(1)
Suggested Readings	183	(1)
Trees	184	(87)
Properties of Trees	184	(10)
Spanning Trees	194	(16)
Depth-First Search	210	(13)
Rooted Trees	223	(9)
Binary Trees and Traversals	232	(14)
Optimal Binary Trees and Binary Search Trees	246	(25)
Historical Notes	265	(1)
Supplementary Exercises	266	(3)
Computer Projects	269	(1)
Suggested Readings	270	(1)
Matching	271	(46)
Systems of Distinct Representatives	271	(6)
Matchings in Graphs	277	(9)
A Matching Algorithm	286	(10)
Applications of the Algorithm	296	(9)
The Hungarian Method	305	(12)
Historical Notes	313	(1)
Supplementary Exercises	313	(2)
Computer Projects	315	(1)
Suggested Readings	316	(1)
Network Flows	317	(43)
Flows and Cuts	317	(11)
A Flow Augmentation Algorithm	328	(13)
The Max-Flow Min-Cut Theorem	341	(6)
Flows and Matchings	347	(13)
Historical Notes	355	(1)
Supplementary Exercises	356	(3)
Computer Projects	359	(1)
Suggested Readings	359	(1)
Counting Techniques	360	(57)
Pascal's Triangle and the Binomial Theorem	360	(5)
Three Fundamental Principles	365	(9)
Permutations and Combinations	374	(5)
Arrangements and Selections with Repetitions	379	(8)
Probability	387	(6)
The Principle of Inclusion-Exclusion	393	(11)
Generating Permutations and r-Combinations	404	(13)
Historical Notes	411	(1)
Supplementary Exercises	412	(3)
Computer Projects	415	(1)
Suggested Readings	416	(1)
Recurrence Relations and Generating Functions	417	(72)
Recurrence Relations	417	(12)
The Method of Iteration	429	(12)
Linear Difference Equations with Constant Coefficients	441	(12)
Analyzing the Efficiency of Algorithms with Recurrence Relations	453	(12)
Counting with Generating Functions	465	(8)
The Algebra of Generating Functions	473	(16)
Historical Notes	483	(1)
Supplementary Exercises	484	(3)
Computer Projects	487	(1)
Suggested Readings	488	(1)
Combinatorial Circuits and Finite State Machines	489	(46)
Logical Gates	489	(10)
Creating Combinatorial Circuits	499	(8)
Karnaugh Maps	507	(14)
Finite State Machines	521	(14)
Historical Notes	530	(1)
Supplementary Exercises	531	(3)
Computer Projects	534	(1)
Suggested Readings	534	(1)
APPENDIX A AN INTRODUCTION TO LOGIC AND PROOF	535	(23)
A.1 Statements and Connectives	535	(9)
A.2 Logical Equivalence	544	(4)
A.3 Methods of Proof	548	(10)
Historical Notes	554	(2)
Supplementary Exercises	556	(1)
Suggested Readings	557	(1)
APPENDIX B MATRICES	558	(8)
Historical Notes	564	(2)
APPENDIX C THE ALGORITHMS IN THIS BOOK	566	(6)
Bibliography	572	(4)
Answers to Odd-Numbered Exercises	576	(39)
Index	615