Discrete Mathematics

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

• ISBN13: 9780321305152
• ISBN10: 0321305159
• Edition: 5th
• Format: Hardcover
• Copyright: 2005-11-18
• Publisher: Pearson

Summary

The strong algorithmic emphasis ofDiscrete Mathematicsis 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

Preface	xi
To the Student	xvii
An Introduction to Combinatorial Problems and Techniques	1	(40)
The Time to Complete a Project	2	(8)
A Matching Problem	10	(6)
A Knapsack Problem	16	(7)
Algorithms and Their Efficiency	23	(18)
Historical Notes	35	(2)
Supplementary Exercises	37	(2)
Computer Projects	39	(1)
Suggested Readings	40	(1)
Sets, Relations, and Functions	41	(58)
Set Operations	41	(6)
Equivalence Relations	47	(7)
Partial Ordering Relations	54	(11)
Functions	65	(11)
Mathematical Induction	76	(8)
Applications	84	(15)
Historical Notes	93	(2)
Supplementary Exercises	95	(3)
Computer Projects	98	(1)
Suggested Readings	98	(1)
Coding Theory	99	(55)
Congruence	100	(6)
The Euclidean Algorithm	106	(7)
The RSA Method	113	(9)
Error-Detecting and Error-Correcting Codes	122	(10)
Matrix Codes	132	(8)
Matrix Codes that Correct All Single-Digit Errors	140	(14)
Historical Notes	147	(2)
Supplementary Exercises	149	(3)
Computer Projects	152	(1)
Suggested Readings	153	(1)
Graphs	154	(74)
Graphs and Their Representations	154	(10)
Paths and Circuits	164	(17)
Shortest Paths and Distance	181	(12)
Coloring a Graph	193	(9)
Directed Graphs and Multigraphs	202	(26)
Historical Notes	219	(1)
Supplementary Exercises	220	(6)
Computer Projects	226	(1)
Suggested Readings	227	(1)
Trees	228	(85)
Properties of Trees	228	(10)
Spanning Trees	238	(15)
Depth-First Search	253	(13)
Rooted Trees	266	(8)
Binary Trees and Traversals	274	(13)
Optimal Binary Trees and Binary Search Trees	287	(26)
Historical Notes	306	(2)
Supplementary Exercises	308	(3)
Computer Projects	311	(1)
Suggested Readings	312	(1)
Matching	313	(45)
Systems of Distinct Representatives	313	(6)
Matchings in Graphs	319	(8)
A Matching Algorithm	327	(10)
Applications of the Algorithm	337	(9)
The Hungarian Method	346	(12)
Historical Notes	354	(1)
Supplementary Exercises	355	(2)
Computer Projects	357	(1)
Suggested Readings	357	(1)
Network Flows	358	(44)
Flows and Cuts	358	(11)
A Flow Augmentation Algorithm	369	(13)
The Max-Flow Min-Cut Theorem	382	(7)
Flows and Matchings	389	(13)
Historical Notes	397	(1)
Supplementary Exercises	397	(3)
Computer Projects	400	(1)
Suggested Readings	401	(1)
Counting Techniques	402	(56)
Pascal's Triangle and the Binomial Theorem	402	(4)
Three Fundamental Principles	406	(10)
Permutations and Combinations	416	(5)
Arrangements and Selections with Repetitions	421	(7)
Probability	428	(6)
The Principle of Inclusion-Exclusion	434	(11)
Generating Permutations and r-Combinations	445	(13)
Historical Notes	452	(1)
Supplementary Exercises	453	(3)
Computer Projects	456	(1)
Suggested Readings	457	(1)
Recurrence Relations and Generating Functions	458	(71)
Recurrence Relations	458	(12)
The Method of Iteration	470	(12)
Linear Difference Equations with Constant Coefficients	482	(12)
Analyzing the Efficiency of Algorithms with Recurrence Relations	494	(12)
Counting with Generating Functions	506	(7)
The Algebra of Generating Functions	513	(16)
Historical Notes	523	(1)
Supplementary Exercises	524	(3)
Computer Projects	527	(1)
Suggested Readings	528	(1)
Combinatorial Circuits and Finite State Machines	529	(45)
Logical Gates	529	(9)
Creating Combinatorial Circuits	538	(8)
Karnaugh Maps	546	(14)
Finite State Machines	560	(14)
Historical Notes	569	(1)
Supplementary Exercises	570	(3)
Computer Projects	573	(1)
Suggested Readings	573	(1)
A. AN INTRODUCTION TO LOGIC AND PROOF	574	(23)
A.1 Statements and Connectives	574	(9)
A.2 Logical Equivalence	583	(4)
A.3 Methods of Proof	587	(10)
Historical Notes	593	(1)
Supplementary Exercises	594	(2)
Suggested Readings	596	(1)
B. MATRICES	597	(10)
Historical Notes	604	(3)
C. THE ALGORITHMS IN THIS BOOK	607	(6)
Bibliography	613	(5)
Answers to Odd-Numbered Exercises	618	(40)
Photo Credits	658	(1)
Index	659