**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

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 OldDirect 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