Discrete Mathematics
International Edition
5th Edition
Published on 9. November 2006
Book
Paperback/Softback
688 pages
978-0-321-38328-0 (ISBN)
Description
An ever-increasing percentage of mathematic applications involve discrete rather than continuous models. Driving this trend is the integration of the computer into virtually every aspect of modern society. Intended for a one-semester introductory course, 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.
More details
Edition
5th edition
Language
English
Place of publication
United States
Publishing group
Pearson Education (US)
Target group
Professional and scholarly
Dimensions
Height: 191 mm
Width: 236 mm
Thickness: 27 mm
Weight
1034 gr
ISBN-13
978-0-321-38328-0 (9780321383280)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Content
(Each Chapter concludes with "Historical Notes," "Supplementary Exercises," "Computer Projects," and "Suggested Readings.").
1: An Introduction to Combinatorial Problems and Techniques
Section 1.1 The Time to Complete a Project
Section 1.2 A Matching Problem
Section 1.3 A Knapsack Problem
Section 1.4 Algorithms and Their Efficiency
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
2: Sets, Relations, and Functions
Section 2.1 Set Operations
Section 2.2 Equivalence Relations
Section 2.3_ Partial Ordering Relations
Section 2.4 Functions
Section 2.5 Mathematical Induction
Section 2.6 Applications
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
3: Coding Theory
Section 3.1 Congruence
Section 3.2 The Euclidean Algorithm and Diophantine Equations
Section 3.3 The RSA Method
Section 3.4 Error-Detecting and Error-Correcting Codes
Section 3.5 Matrix Codes
Section 3.6 Matrix Codes That Correct All Single-Digit Errors
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
4: Graphs
Section 4.1 Graphs and Their Representations
Section 4.2 Paths and Circuits
Section 4.3 Shortest Paths and Distance
Section 4.4 Coloring a Graph
Section 4.5 Directed Graphs and Multigraphs
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
5: Trees
Section 5.1 Properties of Trees
Section 5.2 Spanning Trees
Section 5.3 Depth-First Search
Section 5.4 Rooted Trees
Section 5.5 Binary Trees and Traversals
Section 5.6 Optimal Binary Trees and Binary Search Trees
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
6: Matching
Section 6.1 Systems of Distinct Representatives
Section 6.2 Matchings in Graphs
Section 6.3 A Matching Algorithm
Section 6.4 Applications of the Algorithm
Section 6.5 The Hungarian Method
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
7: Network Flows
Section 7.1 Flows and Cuts
Section 7.2 A Flow Augmentation Algorithm
Section 7.3 The Max-Flow Min-Cut Theorem
Section 7.4 Flows and Matchings
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
8: Counting Techniques
Section 8.1 Pascal's Triangle and the Binomial Theorem
Section 8.3 Permutations and Combinations
Section 8.4 Arrangements and Selections with Repetitions
Section 8.5 Probability
Section 8.6* The Principle of Inclusion-Exclusion
Section 8.7* Generating Permutations and r -Combinations
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
9: Recurrence Relations and Generating Functions
Section 9.1 Recurrence Relations
Section 9.2 The Method of Iteration
Section 9.3 Linear Difference Equations with Constant Coefficients
Section 9.4* Analyzing the Efficiency of Algorithms with Recurrence Relations
Section 9.5 Counting with Generating Functions
Section 9.6 The Algebra of Generating Functions
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
10: Combinatorial Circuits and Finite State Machines
Section 10.1 Logical Gates
Section 10.2 Creating Combinatorial Circuits
Section 10.3 Karnaugh Maps
Section 10.4 Finite State Machines
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
Appendix A: An Introduction to Logic and Proof
Section A.1 Statements and Connectives
Section A.2 Logical Equivalence
Section A.3 Methods of Proof
Historical Notes
Supplementary Exercises
Suggested Readings
Appendix B Matrices
Historical Notes
Appendix C The Algorithms in This Book
Bibliography
Answers to odd-numbered exercises
Index
1: An Introduction to Combinatorial Problems and Techniques
Section 1.1 The Time to Complete a Project
Section 1.2 A Matching Problem
Section 1.3 A Knapsack Problem
Section 1.4 Algorithms and Their Efficiency
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
2: Sets, Relations, and Functions
Section 2.1 Set Operations
Section 2.2 Equivalence Relations
Section 2.3_ Partial Ordering Relations
Section 2.4 Functions
Section 2.5 Mathematical Induction
Section 2.6 Applications
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
3: Coding Theory
Section 3.1 Congruence
Section 3.2 The Euclidean Algorithm and Diophantine Equations
Section 3.3 The RSA Method
Section 3.4 Error-Detecting and Error-Correcting Codes
Section 3.5 Matrix Codes
Section 3.6 Matrix Codes That Correct All Single-Digit Errors
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
4: Graphs
Section 4.1 Graphs and Their Representations
Section 4.2 Paths and Circuits
Section 4.3 Shortest Paths and Distance
Section 4.4 Coloring a Graph
Section 4.5 Directed Graphs and Multigraphs
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
5: Trees
Section 5.1 Properties of Trees
Section 5.2 Spanning Trees
Section 5.3 Depth-First Search
Section 5.4 Rooted Trees
Section 5.5 Binary Trees and Traversals
Section 5.6 Optimal Binary Trees and Binary Search Trees
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
6: Matching
Section 6.1 Systems of Distinct Representatives
Section 6.2 Matchings in Graphs
Section 6.3 A Matching Algorithm
Section 6.4 Applications of the Algorithm
Section 6.5 The Hungarian Method
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
7: Network Flows
Section 7.1 Flows and Cuts
Section 7.2 A Flow Augmentation Algorithm
Section 7.3 The Max-Flow Min-Cut Theorem
Section 7.4 Flows and Matchings
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
8: Counting Techniques
Section 8.1 Pascal's Triangle and the Binomial Theorem
Section 8.3 Permutations and Combinations
Section 8.4 Arrangements and Selections with Repetitions
Section 8.5 Probability
Section 8.6* The Principle of Inclusion-Exclusion
Section 8.7* Generating Permutations and r -Combinations
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
9: Recurrence Relations and Generating Functions
Section 9.1 Recurrence Relations
Section 9.2 The Method of Iteration
Section 9.3 Linear Difference Equations with Constant Coefficients
Section 9.4* Analyzing the Efficiency of Algorithms with Recurrence Relations
Section 9.5 Counting with Generating Functions
Section 9.6 The Algebra of Generating Functions
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
10: Combinatorial Circuits and Finite State Machines
Section 10.1 Logical Gates
Section 10.2 Creating Combinatorial Circuits
Section 10.3 Karnaugh Maps
Section 10.4 Finite State Machines
Historical Notes
Supplementary Exercises
Computer Projects
Suggested Readings
Appendix A: An Introduction to Logic and Proof
Section A.1 Statements and Connectives
Section A.2 Logical Equivalence
Section A.3 Methods of Proof
Historical Notes
Supplementary Exercises
Suggested Readings
Appendix B Matrices
Historical Notes
Appendix C The Algorithms in This Book
Bibliography
Answers to odd-numbered exercises
Index