Discrete Mathematics with Applications, Fifth Edition
By Susanna S. Epp
Contents:Speaking Mathematically 1
Variables 1
Using Variables in Mathematical Discourse; Introduction to Universal, Existential,
and Conditional Statements
The Language of Sets 6
The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products; Strings
The Language of Relations and Functions 15
Definition of a Relation from One Set to Another; Arrow Diagram of a Relation;
Definition of Function; Function Machines; Equality of Functions
The Language of Graphs 24
Definition and Representation of Graphs and Directed Graphs; Degree of a Vertex;
Examples of Graphs Including a Graph Coloring Application
The Logic of Compound Statements 37
Logical Form and Logical Equivalence 37
Statements; Compound Statements; Truth Values; Evaluating the Truth of More General
Compound Statements; Logical Equivalence; Tautologies and Contradictions; Summary
of Logical Equivalences
Conditional Statements 53
Logical Equivalences Involving S; Representation of If-Then As Or; The Negation of
a Conditional Statement; The Contrapositive of a Conditional Statement; The Converse
and Inverse of a Conditional Statement; Only If and the Biconditional; Necessary and
Sufficient Conditions; Remarks
Valid and Invalid Arguments 66
Modus Ponens and Modus Tollens; Additional Valid Argument Forms: Rules of
Inference; Fallacies; Contradictions and Valid Arguments; Summary of Rules of Inference
Application: Digital Logic Circuits 79
Black Boxes and Gates; The Input/Output Table for a Circuit; The Boolean Expression
Corresponding to a Circuit; The Circuit Corresponding to a Boolean Expression; Finding
a Circuit That Corresponds to a Given Input/Output Table; Simplifying Combinational
Circuits; NAND and NOR Gates
Application: Number Systems and Circuits for Addition 93
Binary Representation of Numbers; Binary Addition and Subtraction; Circuits for
Computer Addition; Two’s Complements and the Computer Representation of Negative
Integers; 8-Bit Representation of a Number; Computer Addition with Negative Integers;
Hexadecimal Notation
the Logic of Quantified statements 108
Predicates and Quantified Statements I I08
The Universal Quantifier: 5; The Existential Quantifier: E; Formal versus Informal
Language; Universal Conditional Statements; Equivalent Forms of Universal and
Existential Statements; Bound Variables and Scope; Implicit Quantification; Tarski’s
World
Predicates and Quantified Statements II 122
Negations of Quantified Statements; Negations of Universal Conditional Statements;
The Relation among 5, E, `, and ~; Vacuous Truth of Universal Statements; Variants of
Universal Conditional Statements; Necessary and Sufficient Conditions, Only If
Statements with Multiple Quantifiers 131
Translating from Informal to Formal Language; Ambiguous Language; Negations of
Multiply-Quantified Statements; Order of Quantifiers; Formal Logical Notation; Prolog
Arguments with Quantified Statements 146
Universal Modus Ponens; Use of Universal Modus Ponens in a Proof; Universal Modus
Tollens; Proving Validity of Arguments with Quantified Statements; Using Diagrams to
Test for Validity; Creating Additional Forms of Argument; Remark on the Converse and
Inverse Errors
elementary Number theory and methods
of Proof 160
Direct Proof and Counterexample I: Introduction 161
Definitions; Proving Existential Statements; Disproving Universal Statements by
Counterexample; Proving Universal Statements; Generalizing from the Generic
Particular; Method of Direct Proof; Existential Instantiation; Getting Proofs Started;
Examples
Direct Proof and Counterexample II: Writing Advice 173
Writing Proofs of Universal Statements; Common Mistakes; Examples; Showing That an
Existential Statement Is False; Conjecture, Proof, and Disproof
Direct Proof and Counterexample III: Rational Numbers 183
More on Generalizing from the Generic Particular; Proving Properties of Rational
Numbers; Deriving New Mathematics from Old
Direct Proof and Counterexample IV: Divisibility 190
Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique
Factorization of Integers Theorem
Direct Proof and Counterexample V: Division into Cases and the
Quotient-Remainder Theorem 200
Discussion of the Quotient-Remainder Theorem and Examples; div and mod; Alternative
Representations of Integers and Applications to Number Theory; Absolute Value and the
Triangle Inequality
Direct Proof and Counterexample VI: Floor and Ceiling 211
Definition and Basic Properties; The Floor of ny2
Indirect Argument: Contradiction and Contraposition 218
Proof by Contradiction; Argument by Contraposition; Relation between Proof by
Contradiction and Proof by Contraposition; Proof as a Problem-Solving Tool
Indirect Argument: Two Famous Theorems 228
The Irrationality of Ï2; Are There Infinitely Many Prime Numbers?; When to Use
Indirect Proof; Open Questions in Number Theory
Application: The handshake Theorem 235
The Total Degree of a Graph; The Handshake Theorem and Consequences; Applications;
Simple Graphs; Complete Graphs; Bipartite Graphs
Application: Algorithms 244
An Algorithmic Language; A Notation for Algorithms; Trace Tables; The Division
Algorithm; The Euclidean Algorithm
sequences, mathematical induction,
and recursion 258
Sequences 258
Explicit Formulas for Sequences; Summation Notation; Product Notation; Properties
of Summations and Products; Change of Variable; Factorial and n Choose r Notation;
Sequences in Computer Programming; Application: Algorithm to Convert from Base 10
to Base 2 Using Repeated Division by 2
Mathematical Induction I: Proving Formulas 275
Principle of Mathematical Induction; Sum of the First n Integers; Proving an Equality;
Deducing Additional Formulas; Sum of a Geometric Sequence
Mathematical Induction II: Applications 289
Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibility
Properties; Proving Inequalities; Trominoes and Other Applications
Strong Mathematical Induction and the Well-Ordering
Principle for the Integers 301
Strong Mathematical Induction; The Well-Ordering Principle for the Integers; Binary
Representation of Integers and Other Applications
Application: Correctness of Algorithms 314
Assertions; Loop Invariants; Correctness of the Division Algorithm; Correctness of the
Euclidean Theorem
Defining Sequences Recursively 325
Examples of Recursively Defined Sequences; Recursive Definitions of Sum and Product
Solving Recurrence Relations by Iteration 340
The Method of Iteration; Using Formulas to Simplify Solutions Obtained by Iteration;
Checking the Correctness of a Formula by Mathematical Induction; Discovering That an
Explicit Formula Is Incorrect
Second-Order Linear homogeneous Recurrence Relations
with Constant Coefficients 352
Derivation of a Technique for Solving These Relations; The Distinct-Roots Case; The
Single-Root Case
General Recursive Definitions and Structural Induction 364
Recursively Defined Sets; Recursive Definitions for Boolean Expressions, Strings, and
Parenthesis Structures; Using Structural Induction to Prove Properties about Recursively
Defined Sets; Recursive Functions
set theory 377
Set Theory: Definitions and the Element Method of Proof 377
Subsets: Introduction to Proof and Disproof for Sets; Set Equality; Venn Diagrams;
Operations on Sets; The Empty Set; Partitions of Sets; Power Sets; An Algorithm to
Check Whether One Set Is a Subset of Another (Optional)
Properties of Sets 391
Set Identities; Proving Subset Relations and Set Equality; Proving That a Set Is the
Empty Set
Disproofs and Algebraic Proofs 407
Disproving an Alleged Set Property; Problem-Solving Strategy; The Number of Subsets
of a Set; “Algebraic” Proofs of Set Identities
Boolean Algebras, Russell’s Paradox, and the halting Problem 414
Boolean Algebras: Definition and Properties; Russell’s Paradox; The Halting Problem
Properties of Functions 425
Functions Defined on General Sets 425
Dynamic Function Terminology; Equality of Functions; Additional Examples of
Functions; Boolean Functions; Checking Whether a Function Is Well Defined; Functions
Acting on Sets
One-to-One, Onto, and Inverse Functions 439
One-to-One Functions; One-to-One Functions on Infinite Sets; Application: Hash
Functions and Cryptographic Hash Functions; Onto Functions; Onto Functions on
Infinite Sets; Relations between Exponential and Logarithmic Functions; One-to-One
Correspondences; Inverse Functions
Composition of Functions 461
Definition and Examples; Composition of One-to-One Functions; Composition of Onto
Functions
Cardinality with Applications to Computability 473
Definition of Cardinal Equivalence; Countable Sets; The Search for Larger Infinities: The
Cantor Diagonalization Process; Application: Cardinality and Computability
Properties of relations 487
Relations on Sets 487
Additional Examples of Relations; The Inverse of a Relation; Directed Graph of a
Relation; N-ary Relations and Relational Databases
Reflexivity, Symmetry, and Transitivity 495
Reflexive, Symmetric, and Transitive Properties; Properties of Relations on Infinite Sets;
The Transitive Closure of a Relation
Equivalence Relations 505
The Relation Induced by a Partition; Definition of an Equivalence Relation; Equivalence
Classes of an Equivalence Relation
Modular Arithmetic with Applications to Cryptography 524
Properties of Congruence Modulo n; Modular Arithmetic; Extending the Euclidean
Algorithm; Finding an Inverse Modulo n; RSA Cryptography; Euclid’s Lemma; Fermat’s
Little Theorem; Why Does the RSA Cipher Work?; Message Authentication; Additional
Remarks on Number Theory and Cryptography
Partial Order Relations 546
Antisymmetry; Partial Order Relations; Lexicographic Order; Hasse Diagrams; Partially
and Totally Ordered Sets; Topological Sorting; An Application; PERT and CPM
counting and Probability 564
Introduction to Probability 564
Definition of Sample Space and Event; Probability in the Equally Likely Case; Counting
the Elements of Lists, Sublists, and One-Dimensional Arrays
Possibility Trees and the Multiplication Rule 573
Possibility Trees; The Multiplication Rule; When the Multiplication Rule Is Difficult or
Impossible to Apply; Permutations; Permutations of Selected Elements
Counting Elements of Disjoint Sets: The Addition Rule 589
The Addition Rule; The Difference Rule; The Inclusion/Exclusion Rule
The Pigeonhole Principle 604
Statement and Discussion of the Principle; Applications; Decimal Expansions of
Fractions; Generalized Pigeonhole Principle; Proof of the Pigeonhole Principle
Counting Subsets of a Set: Combinations 617
r-Combinations; Ordered and Unordered Selections; Relation between Permutations
and Combinations; Permutation of a Set with Repeated Elements; Some Advice about
Counting; The Number of Partitions of a Set into r Subsets
r-Combinations with Repetition Allowed 634
Multisets and How to Count Them; Which Formula to Use?
Pascal’s Formula and the Binomial Theorem 642
Combinatorial Formulas; Pascal’s Triangle; Algebraic and Combinatorial Proofs of
Pascal’s Formula; The Binomial Theorem and Algebraic and Combinatorial Proofs for It;
Applications
Probability Axioms and Expected Value 655
Probability Axioms; Deriving Additional Probability Formulas; Expected Value
Conditional Probability, Bayes’ Formula, and Independent Events 662
Conditional Probability; Bayes’ Theorem; Independent Events
theory of Graphs and trees 677
Trails, Paths, and Circuits 677
Definitions; Connectedness; Euler Circuits; Hamiltonian Circuits
Matrix Representations of Graphs 698
Matrices; Matrices and Directed Graphs; Matrices and Undirected Graphs; Matrices and
Connected Components; Matrix Multiplication; Counting Walks of Length N
Isomorphisms of Graphs 713
Definition of Graph Isomorphism and Examples; Isomorphic Invariants; Graph
Isomorphism for Simple Graphs
Trees: Examples and Basic Properties 720
Definition and Examples of Trees; Characterizing Trees
Rooted Trees 732
Definition and Examples of Rooted Trees; Binary Trees and Their Properties; Binary
Search Trees
Spanning Trees and a Shortest Path Algorithm 742
Definition of a Spanning Tree; Minimum Spanning Trees; Kruskal’s Algorithm; Prim’s
Algorithm; Dijkstra’s Shortest Path Algorithm
analysis of algorithm efficiency 760
Real-Valued Functions of a Real Variable and Their Graphs 760
Graph of a Function; Power Functions; The Floor Function; Graphing Functions Defined
on Sets of Integers; Graph of a Multiple of a Function; Increasing and Decreasing
Functions
Big-O, Big-Omega, and Big-Theta Notations 769
Definition and General Properties of O-, V-, and Q-Notations; Orders of Power
Functions; Orders of Polynomial Functions; A Caution about O-Notation; Theorems
about Order Notation
Application: Analysis of Algorithm Efficiency I 787
Measuring the Efficiency of an Algorithm; Computing Orders of Simple Algorithms;
The Sequential Search Algorithm; The Insertion Sort Algorithm; Time Efficiency of an
Algorithm
Exponential and Logarithmic Functions: Graphs and Orders 800
Graphs of Exponential and Logarithmic Functions; Application: Number of Bits Needed
to Represent an Integer in Binary Notation; Application: Using Logarithms to Solve
Recurrence Relations; Exponential and Logarithmic Orders
Application: Analysis of Algorithm Efficiency II 813
Binary Search; Divide-and-Conquer Algorithms; The Efficiency of the Binary Search
Algorithm; Merge Sort; Tractable and Intractable Problems; A Final Remark on
Algorithm Efficiency
regular expressions and Finite-state automata 828
Formal Languages and Regular Expressions 829
Definitions and Examples of Formal Languages and Regular Expressions; The Language
Defined by a Regular Expression; Practical Uses of Regular Expressions
Finite-State Automata 841
Definition of a Finite-State Automaton; The Language Accepted by an Automaton; The
Eventual-State Function; Designing a Finite-State Automaton; Simulating a Finite-State
Automaton Using Software; Finite-State Automata and Regular Expressions; Regular
Languages
Simplifying Finite-State Automata 858
*-Equivalence of States; k-Equivalence of States; Finding the *-Equivalence Classes; The
Quotient Automaton; Constructing the Quotient Automaton; Equivalent Automata
Properties of the real Numbers a-1
solutions and hints to selected exercises a-4
Index I-1
Variables 1
Using Variables in Mathematical Discourse; Introduction to Universal, Existential,
and Conditional Statements
The Language of Sets 6
The Set-Roster and Set-Builder Notations; Subsets; Cartesian Products; Strings
The Language of Relations and Functions 15
Definition of a Relation from One Set to Another; Arrow Diagram of a Relation;
Definition of Function; Function Machines; Equality of Functions
The Language of Graphs 24
Definition and Representation of Graphs and Directed Graphs; Degree of a Vertex;
Examples of Graphs Including a Graph Coloring Application
The Logic of Compound Statements 37
Logical Form and Logical Equivalence 37
Statements; Compound Statements; Truth Values; Evaluating the Truth of More General
Compound Statements; Logical Equivalence; Tautologies and Contradictions; Summary
of Logical Equivalences
Conditional Statements 53
Logical Equivalences Involving S; Representation of If-Then As Or; The Negation of
a Conditional Statement; The Contrapositive of a Conditional Statement; The Converse
and Inverse of a Conditional Statement; Only If and the Biconditional; Necessary and
Sufficient Conditions; Remarks
Valid and Invalid Arguments 66
Modus Ponens and Modus Tollens; Additional Valid Argument Forms: Rules of
Inference; Fallacies; Contradictions and Valid Arguments; Summary of Rules of Inference
Application: Digital Logic Circuits 79
Black Boxes and Gates; The Input/Output Table for a Circuit; The Boolean Expression
Corresponding to a Circuit; The Circuit Corresponding to a Boolean Expression; Finding
a Circuit That Corresponds to a Given Input/Output Table; Simplifying Combinational
Circuits; NAND and NOR Gates
Application: Number Systems and Circuits for Addition 93
Binary Representation of Numbers; Binary Addition and Subtraction; Circuits for
Computer Addition; Two’s Complements and the Computer Representation of Negative
Integers; 8-Bit Representation of a Number; Computer Addition with Negative Integers;
Hexadecimal Notation
the Logic of Quantified statements 108
Predicates and Quantified Statements I I08
The Universal Quantifier: 5; The Existential Quantifier: E; Formal versus Informal
Language; Universal Conditional Statements; Equivalent Forms of Universal and
Existential Statements; Bound Variables and Scope; Implicit Quantification; Tarski’s
World
Predicates and Quantified Statements II 122
Negations of Quantified Statements; Negations of Universal Conditional Statements;
The Relation among 5, E, `, and ~; Vacuous Truth of Universal Statements; Variants of
Universal Conditional Statements; Necessary and Sufficient Conditions, Only If
Statements with Multiple Quantifiers 131
Translating from Informal to Formal Language; Ambiguous Language; Negations of
Multiply-Quantified Statements; Order of Quantifiers; Formal Logical Notation; Prolog
Arguments with Quantified Statements 146
Universal Modus Ponens; Use of Universal Modus Ponens in a Proof; Universal Modus
Tollens; Proving Validity of Arguments with Quantified Statements; Using Diagrams to
Test for Validity; Creating Additional Forms of Argument; Remark on the Converse and
Inverse Errors
elementary Number theory and methods
of Proof 160
Direct Proof and Counterexample I: Introduction 161
Definitions; Proving Existential Statements; Disproving Universal Statements by
Counterexample; Proving Universal Statements; Generalizing from the Generic
Particular; Method of Direct Proof; Existential Instantiation; Getting Proofs Started;
Examples
Direct Proof and Counterexample II: Writing Advice 173
Writing Proofs of Universal Statements; Common Mistakes; Examples; Showing That an
Existential Statement Is False; Conjecture, Proof, and Disproof
Direct Proof and Counterexample III: Rational Numbers 183
More on Generalizing from the Generic Particular; Proving Properties of Rational
Numbers; Deriving New Mathematics from Old
Direct Proof and Counterexample IV: Divisibility 190
Proving Properties of Divisibility; Counterexamples and Divisibility; The Unique
Factorization of Integers Theorem
Direct Proof and Counterexample V: Division into Cases and the
Quotient-Remainder Theorem 200
Discussion of the Quotient-Remainder Theorem and Examples; div and mod; Alternative
Representations of Integers and Applications to Number Theory; Absolute Value and the
Triangle Inequality
Direct Proof and Counterexample VI: Floor and Ceiling 211
Definition and Basic Properties; The Floor of ny2
Indirect Argument: Contradiction and Contraposition 218
Proof by Contradiction; Argument by Contraposition; Relation between Proof by
Contradiction and Proof by Contraposition; Proof as a Problem-Solving Tool
Indirect Argument: Two Famous Theorems 228
The Irrationality of Ï2; Are There Infinitely Many Prime Numbers?; When to Use
Indirect Proof; Open Questions in Number Theory
Application: The handshake Theorem 235
The Total Degree of a Graph; The Handshake Theorem and Consequences; Applications;
Simple Graphs; Complete Graphs; Bipartite Graphs
Application: Algorithms 244
An Algorithmic Language; A Notation for Algorithms; Trace Tables; The Division
Algorithm; The Euclidean Algorithm
sequences, mathematical induction,
and recursion 258
Sequences 258
Explicit Formulas for Sequences; Summation Notation; Product Notation; Properties
of Summations and Products; Change of Variable; Factorial and n Choose r Notation;
Sequences in Computer Programming; Application: Algorithm to Convert from Base 10
to Base 2 Using Repeated Division by 2
Mathematical Induction I: Proving Formulas 275
Principle of Mathematical Induction; Sum of the First n Integers; Proving an Equality;
Deducing Additional Formulas; Sum of a Geometric Sequence
Mathematical Induction II: Applications 289
Comparison of Mathematical Induction and Inductive Reasoning; Proving Divisibility
Properties; Proving Inequalities; Trominoes and Other Applications
Strong Mathematical Induction and the Well-Ordering
Principle for the Integers 301
Strong Mathematical Induction; The Well-Ordering Principle for the Integers; Binary
Representation of Integers and Other Applications
Application: Correctness of Algorithms 314
Assertions; Loop Invariants; Correctness of the Division Algorithm; Correctness of the
Euclidean Theorem
Defining Sequences Recursively 325
Examples of Recursively Defined Sequences; Recursive Definitions of Sum and Product
Solving Recurrence Relations by Iteration 340
The Method of Iteration; Using Formulas to Simplify Solutions Obtained by Iteration;
Checking the Correctness of a Formula by Mathematical Induction; Discovering That an
Explicit Formula Is Incorrect
Second-Order Linear homogeneous Recurrence Relations
with Constant Coefficients 352
Derivation of a Technique for Solving These Relations; The Distinct-Roots Case; The
Single-Root Case
General Recursive Definitions and Structural Induction 364
Recursively Defined Sets; Recursive Definitions for Boolean Expressions, Strings, and
Parenthesis Structures; Using Structural Induction to Prove Properties about Recursively
Defined Sets; Recursive Functions
set theory 377
Set Theory: Definitions and the Element Method of Proof 377
Subsets: Introduction to Proof and Disproof for Sets; Set Equality; Venn Diagrams;
Operations on Sets; The Empty Set; Partitions of Sets; Power Sets; An Algorithm to
Check Whether One Set Is a Subset of Another (Optional)
Properties of Sets 391
Set Identities; Proving Subset Relations and Set Equality; Proving That a Set Is the
Empty Set
Disproofs and Algebraic Proofs 407
Disproving an Alleged Set Property; Problem-Solving Strategy; The Number of Subsets
of a Set; “Algebraic” Proofs of Set Identities
Boolean Algebras, Russell’s Paradox, and the halting Problem 414
Boolean Algebras: Definition and Properties; Russell’s Paradox; The Halting Problem
Properties of Functions 425
Functions Defined on General Sets 425
Dynamic Function Terminology; Equality of Functions; Additional Examples of
Functions; Boolean Functions; Checking Whether a Function Is Well Defined; Functions
Acting on Sets
One-to-One, Onto, and Inverse Functions 439
One-to-One Functions; One-to-One Functions on Infinite Sets; Application: Hash
Functions and Cryptographic Hash Functions; Onto Functions; Onto Functions on
Infinite Sets; Relations between Exponential and Logarithmic Functions; One-to-One
Correspondences; Inverse Functions
Composition of Functions 461
Definition and Examples; Composition of One-to-One Functions; Composition of Onto
Functions
Cardinality with Applications to Computability 473
Definition of Cardinal Equivalence; Countable Sets; The Search for Larger Infinities: The
Cantor Diagonalization Process; Application: Cardinality and Computability
Properties of relations 487
Relations on Sets 487
Additional Examples of Relations; The Inverse of a Relation; Directed Graph of a
Relation; N-ary Relations and Relational Databases
Reflexivity, Symmetry, and Transitivity 495
Reflexive, Symmetric, and Transitive Properties; Properties of Relations on Infinite Sets;
The Transitive Closure of a Relation
Equivalence Relations 505
The Relation Induced by a Partition; Definition of an Equivalence Relation; Equivalence
Classes of an Equivalence Relation
Modular Arithmetic with Applications to Cryptography 524
Properties of Congruence Modulo n; Modular Arithmetic; Extending the Euclidean
Algorithm; Finding an Inverse Modulo n; RSA Cryptography; Euclid’s Lemma; Fermat’s
Little Theorem; Why Does the RSA Cipher Work?; Message Authentication; Additional
Remarks on Number Theory and Cryptography
Partial Order Relations 546
Antisymmetry; Partial Order Relations; Lexicographic Order; Hasse Diagrams; Partially
and Totally Ordered Sets; Topological Sorting; An Application; PERT and CPM
counting and Probability 564
Introduction to Probability 564
Definition of Sample Space and Event; Probability in the Equally Likely Case; Counting
the Elements of Lists, Sublists, and One-Dimensional Arrays
Possibility Trees and the Multiplication Rule 573
Possibility Trees; The Multiplication Rule; When the Multiplication Rule Is Difficult or
Impossible to Apply; Permutations; Permutations of Selected Elements
Counting Elements of Disjoint Sets: The Addition Rule 589
The Addition Rule; The Difference Rule; The Inclusion/Exclusion Rule
The Pigeonhole Principle 604
Statement and Discussion of the Principle; Applications; Decimal Expansions of
Fractions; Generalized Pigeonhole Principle; Proof of the Pigeonhole Principle
Counting Subsets of a Set: Combinations 617
r-Combinations; Ordered and Unordered Selections; Relation between Permutations
and Combinations; Permutation of a Set with Repeated Elements; Some Advice about
Counting; The Number of Partitions of a Set into r Subsets
r-Combinations with Repetition Allowed 634
Multisets and How to Count Them; Which Formula to Use?
Pascal’s Formula and the Binomial Theorem 642
Combinatorial Formulas; Pascal’s Triangle; Algebraic and Combinatorial Proofs of
Pascal’s Formula; The Binomial Theorem and Algebraic and Combinatorial Proofs for It;
Applications
Probability Axioms and Expected Value 655
Probability Axioms; Deriving Additional Probability Formulas; Expected Value
Conditional Probability, Bayes’ Formula, and Independent Events 662
Conditional Probability; Bayes’ Theorem; Independent Events
theory of Graphs and trees 677
Trails, Paths, and Circuits 677
Definitions; Connectedness; Euler Circuits; Hamiltonian Circuits
Matrix Representations of Graphs 698
Matrices; Matrices and Directed Graphs; Matrices and Undirected Graphs; Matrices and
Connected Components; Matrix Multiplication; Counting Walks of Length N
Isomorphisms of Graphs 713
Definition of Graph Isomorphism and Examples; Isomorphic Invariants; Graph
Isomorphism for Simple Graphs
Trees: Examples and Basic Properties 720
Definition and Examples of Trees; Characterizing Trees
Rooted Trees 732
Definition and Examples of Rooted Trees; Binary Trees and Their Properties; Binary
Search Trees
Spanning Trees and a Shortest Path Algorithm 742
Definition of a Spanning Tree; Minimum Spanning Trees; Kruskal’s Algorithm; Prim’s
Algorithm; Dijkstra’s Shortest Path Algorithm
analysis of algorithm efficiency 760
Real-Valued Functions of a Real Variable and Their Graphs 760
Graph of a Function; Power Functions; The Floor Function; Graphing Functions Defined
on Sets of Integers; Graph of a Multiple of a Function; Increasing and Decreasing
Functions
Big-O, Big-Omega, and Big-Theta Notations 769
Definition and General Properties of O-, V-, and Q-Notations; Orders of Power
Functions; Orders of Polynomial Functions; A Caution about O-Notation; Theorems
about Order Notation
Application: Analysis of Algorithm Efficiency I 787
Measuring the Efficiency of an Algorithm; Computing Orders of Simple Algorithms;
The Sequential Search Algorithm; The Insertion Sort Algorithm; Time Efficiency of an
Algorithm
Exponential and Logarithmic Functions: Graphs and Orders 800
Graphs of Exponential and Logarithmic Functions; Application: Number of Bits Needed
to Represent an Integer in Binary Notation; Application: Using Logarithms to Solve
Recurrence Relations; Exponential and Logarithmic Orders
Application: Analysis of Algorithm Efficiency II 813
Binary Search; Divide-and-Conquer Algorithms; The Efficiency of the Binary Search
Algorithm; Merge Sort; Tractable and Intractable Problems; A Final Remark on
Algorithm Efficiency
regular expressions and Finite-state automata 828
Formal Languages and Regular Expressions 829
Definitions and Examples of Formal Languages and Regular Expressions; The Language
Defined by a Regular Expression; Practical Uses of Regular Expressions
Finite-State Automata 841
Definition of a Finite-State Automaton; The Language Accepted by an Automaton; The
Eventual-State Function; Designing a Finite-State Automaton; Simulating a Finite-State
Automaton Using Software; Finite-State Automata and Regular Expressions; Regular
Languages
Simplifying Finite-State Automata 858
*-Equivalence of States; k-Equivalence of States; Finding the *-Equivalence Classes; The
Quotient Automaton; Constructing the Quotient Automaton; Equivalent Automata
Properties of the real Numbers a-1
solutions and hints to selected exercises a-4
Index I-1