Discrete Mathematics with Applications

✍ Scribed by Thomas Koshy

• Publisher: Elsevier Academic Press
• Year: 2004
• Tongue: English
• Leaves: 1079
• Edition: 1
• Category: Library

✦ Table of Contents

Front Cover
Discrete Mathematicswith Applications
Copyright Page
Table of Contents
Preface
A Word to the Student
Chapter 1. The Language of Logic
1.1 Propositions
1.2 Logical Equivalences
1.3 Quantifiers
1
.4 Arguments (optional)
1.5 Proof Methods
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter 2. The Language of Sets
2.1 The Concept of a Set
2.2 Operations with Sets
2.3 Computer Operations with
Sets (optional)
2.4 The Cardinality of a Set
2.5 Recursively Defined Sets
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter
3. Functions and Matrices
3.1 The Concept of a Function
3.2 Special Functions
3.3 Properties of Functions
3.4 The Pigeonhole Principle
3.5 Composition of Functions
3.6 Sequences and the Summation Notation
3.7 Matrices
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter 4. Induction and Algorithms
4.1 The Division Algorithm
4.2 Divisibility Properties
4.3 Nondecimal Bases
4.4 Mathematical Induction
4.5 Algorithm Correctness
4.6 The Growth of Functions
4
.7 Complexities of Algorithms (optional)
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter
5. Recursion
5.1 Recursively Defined Functions
5.2 Solving Recurrence Relations
5.3 Solving Recurrence Relations Revisited
5.4 Generating Functions
5.5 Recursive Algorithms
5.6 Correctness of Recursive Algorithms
5.7 Complexities of Recursive Algorithms
(optional)
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter 6.
Combinatorics and Discrete Probability
6.1 The Fundamental Counting Principles
6.2 Permutations
6.3 Derangements
6.4 Combinations
6.5 Permutations and Combinations with Repetitions
6.6 The Binomial Theorem
6.7 The Generalized Inclusion–Exclusion Principle (GIEP) (optional)
6.8 Discrete Probability (optional)
6.9 Additional Topics in Probability (optional)
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter
7. Relations
7.1 Boolean Matrices
7.2 Relations and Digraphs
7.3 Computer Representations of Relations (optional)
7.4 Properties of Relations
7.5 Operations on Relations
7.6 The Connectivity Relation (optional)
7.7 Transitive Closure (optional)
7.8 Equivalence
Relations
7.9 Partial and Total Orderings
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter 8. Graphs
8.1 Graphs
8.2 Computer Representations of Graphs (optional)
8.3 Isomorphic Graphs
8.4 Paths, Cycles, and Circuits
8.5 Eulerian and Hamiltonian Graphs
8.6 Planar Graphs
8.7 Graph Coloring
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter 9. Trees
9.1 Trees
9.2 Spanning trees
9.3 Minimal Spanning Trees
9.4 Rooted Trees
9.5 Binary Trees
9.6 Binary Search Trees
9.7 Huffman Trees (optional)
9.8 Decision Trees (optional)
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter 10.
Digraphs
10.1 Digraphs
10.2 Dags
10.3 Weighted Digraphs
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter 11. Formal Languages and Finite-State Machines
11.1 Formal Languages
11.2 Grammars
11.3 Finite-State Automata
11.4 Finite-State Machines
11.5 Deterministic Finite-State Automata and Regular Languages
11.6 Nondeterministic Finite-State Automata
11.7 Automata and Regular Languages
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Chapter 12. Boolean Algebra and Combinatorial Circuits
12.1 Boolean Algebra
12.2 Boolean functions
12.3 Logic Gates
12.4 Combinatorial Circuits
12.5 Minimization of Combinatorial Circuits
12.6 Don’t Care Conditions
Chapter Summary
Review Exercises
Supplementary Exercises
Computer Exercises
Exploratory Writing Projects
Enrichment Readings
Appendix A
A.1 ASCII Character Set
A.2 Determinants
A.3 Exponential and Logarithmic Functions
A.4 Generating Permutations and Combinations
A.5 The Multinomial Theorem
A.6 The Greek Alphabet
A.7 Web Sites
References
Solutions to Odd-Numbered Exercises
Credits
Index
List of Biographical Sketches
Application Index
Alogrithms Index
List of Symbols