Discrete Mathematics

by Johnsonbaugh, Richard

• ISBN13: 9780130890085
• ISBN10: 0130890081
• Edition: 5th
• Format: Hardcover
• Copyright: 2001-01-01
• Publisher: Pearson College Div

Summary

For one or two term introductory courses in discrete mathematics. This best-selling book provides an accessible introduction to discrete mathematics through an algorithmic approach that focuses on problem- solving techniques. This edition has woven techniques of proofs into the text as a running theme. Each chapter has a problem-solving corner that shows students how to attack and solve problems.

Table of Contents

Preface	ix
Logic and Proofs	1	(54)
Propositions	2	(5)
Conditional Propositions and Logical Equivalence	7	(7)
Quantifiers	14	(15)
Proofs	29	(8)
Resolution Proofs	37	(4)
Mathematical Induction	41	(14)
Problem-Solving Corner: Mathematical Induction	49	(2)
Notes	51	(1)
Chapter Review	51	(2)
Chapter Self-Test	53	(1)
Computer Exercises	54	(1)
The Language of Mathematics	55	(65)
Sets	56	(8)
Sequences and Strings	64	(7)
Number Systems	71	(6)
Relations	77	(8)
Problem-Solving Corner: Relations	84	(1)
Equivalence Relations	85	(7)
Problem-Solving Corner: Equivalence Relations	90	(2)
Matrices of Relations	92	(5)
Relational Databases	97	(4)
Functions	101	(19)
Notes	114	(1)
Chapter Review	114	(2)
Chapter Self-Test	116	(2)
Computer Exercises	118	(2)
Algorithms	120	(45)
Introduction	121	(1)
Notation for Algorithms	122	(6)
The Euclidean Algorithm	128	(4)
Recursive Algorithms	132	(6)
Complexity of Algorithms	138	(16)
Problem-Solving Corner: Design and Analysis of an Algorithm	152	(2)
Analysis of the Euclidean Algorithm	154	(3)
The RSA Public-Key Cryptosystem	157	(8)
Notes	160	(1)
Chapter Review	161	(1)
Chapter Self-Test	162	(2)
Computer Exercises	164	(1)
Counting Methods and the Pigeonhole Principle	165	(59)
Basic Principles	165	(9)
Problem-Solving Corner: Counting	172	(2)
Permutations and Combinations	174	(13)
Problem-Solving Corner: Combinations	185	(2)
Algorithms for Generating Permutations and Combinations	187	(5)
Introduction to Discrete Probability	192	(3)
Discrete Probability Theory	195	(11)
Generalized Permutations and Combinations	206	(5)
Binomial Coefficients and Combinatorial Identities	211	(5)
The Pigeonhole Principle	216	(8)
Notes	220	(1)
Chapter Review	220	(1)
Chapter Self-Test	221	(2)
Computer Exercises	223	(1)
Recurrence Relations	224	(39)
Introduction	224	(11)
Solving Recurrence Relations	235	(14)
Problem-Solving Corner: Recurrence Relations	246	(3)
Applications to the Analysis of Algorithms	249	(14)
Notes	260	(1)
Chapter Review	260	(1)
Chapter Self-Test	260	(1)
Computer Exercises	261	(2)
Graph Theory	263	(60)
Introduction	263	(11)
Paths and Cycles	274	(11)
Problem-Solving Corner: Graphs	284	(1)
Hamiltonian Cycles and the Traveling Salesperson Problem	285	(6)
A Shortest-Path Algorithm	291	(5)
Representations of Graphs	296	(5)
Isomorphisms of Graphs	301	(6)
Planar Graphs	307	(6)
Instant Insanity	313	(10)
Notes	317	(1)
Chapter Review	317	(2)
Chapter Self-Test	319	(2)
Computer Exercises	321	(2)
Trees	323	(67)
Introduction	323	(8)
Terminology and Characterizations of Trees	331	(6)
Problem-Solving Corner: Trees	336	(1)
Spanning Trees	337	(6)
Minimal Spanning Trees	343	(6)
Binary Trees	349	(6)
Tree Traversals	355	(6)
Decision Trees and the Minimum Time for Sorting	361	(6)
Isomorphism of Trees	367	(9)
Game Trees	376	(14)
Notes	384	(1)
Chapter Review	384	(1)
Chapter Self-Test	385	(4)
Computer Exercises	389	(1)
Network Models	390	(26)
Introduction	390	(6)
A Maximal Flow Algorithm	396	(8)
The Max Flow, Min Cut Theorem	404	(3)
Matching	407	(9)
Problem-Solving Corner: Matching	412	(1)
Notes	413	(1)
Chapter Review	414	(1)
Chapter Self-Test	414	(1)
Computer Exercises	415	(1)
Boolean Algebras and Combinatorial Circuits	416	(36)
Combinatorial Circuits	416	(7)
Properties of Combinatorial Circuits	423	(4)
Boolean Algebras	427	(7)
Problem-Solving Corner: Boolean Algebras	432	(2)
Boolean Functions and Synthesis of Circuits	434	(5)
Applications	439	(13)
Notes	447	(1)
Chapter Review	447	(1)
Chapter Self-Test	448	(2)
Computer Exercises	450	(2)
Automata, Grammars, and Languages	452	(37)
Sequential Circuits and Finite-State Machines	452	(6)
Finite-State Automata	458	(6)
Languages and Grammars	464	(8)
Nondeterministic Finite-State Automata	472	(7)
Relationships Between Languages and Automata	479	(10)
Notes	484	(1)
Chapter Review	485	(1)
Chapter Self-Test	486	(2)
Computer Exercises	488	(1)
Computational Geometry	489	(16)
The Closest-Pair Problem	489	(5)
A Lower Bound for the Closest-Pair Problem	494	(2)
An Algorithm to Compute the Convex Hull	496	(9)
Notes	503	(1)
Chapter Review	503	(1)
Chapter Self-Test	503	(1)
Computer Exercises	504	(1)
A Matrices	505	(4)
B Algebra Review	509	(12)
References	521	(6)
Hints and Solutions to Selected Exercises	527	(80)
Index	607