Math 19 Course Topics

 

Discrete Mathematics with Applications, 2nd edition.

by Susanna S. Epp, Brooks/Cole Publishing Company

 

Categories:  1.  Must be covered in detail

                  2.  Must be covered at least briefly

                  3.  Do not cover unless you have extra time after adequately

                       doing 1 and 2.

 

Category          Section                                                 Section Topics

 

 

 

 

1

1.1

Logical Form and Logical Equivalence

1

1.2

Conditional Statements

1

1.3

Valid and Invalid Arguments

2

1.4

Applications:  Digital Logic Circuits

2

1.5

Applications:  Number Systems

                     and Circuits for Addition

 

 

 

 

 

 

1

2.1

Predicates and Quantified Statements I

1

2.2

Predicates and Quantified Statements II

1

2.3

Arguments with Quantified Statements

 

 

 

 

 

 

1

3.1

Direct Proof and Counterexample I:  Introduction

1

3.2

Direct Proof and Counterexample II:  Rational Numbers

1

3.3

Direct Proof and Counterexample III:  Divisibility

1

3.4

Direct Proof and Counterexample IV: 

      Division into Cases and the Quotient-Remainder Theorem

1

3.5

Direct Proof and Counterexample V:  Floor and Ceiling

1

3.6

Indirect Argument:  Contradiction and Contraposition

2

3.7

Two Classic Theorems

2

3.8

Algorithms  (optional handouts available on classic

      algorithms, sorting algorithms, and recursive algorithms)

 

 

 

1

4.1

Sequences

1

4.2

Mathematical Induction I

1

4.3

Mathematical Induction II

1

4.4

Strong Mathematical Induction and the Well-Ordering Principle

2

4.5

Application:  Correctness of Algorithms

 

 

 

 

 

 

1

5.1

Basic Definitions of Set Theory

1

5.2

Properties of Sets

1

5.3

The Empty Set, Partitions, Power Sets, and Boolean Algebras

3

5.4

Russell's Paradox and the Halting Problem

 

 

 

 

 

 

1

6.1

Counting and Probability

1

6.2

Possibility Trees and the Multiplication Rule

1

6.3

Counting Elements of Disjoint Sets:  The Addition Rule

1

6.4

Counting Subsets of a Set:  Combinations

1

6.5

R-Combinations with Repetitions Allowed

1

6.6

The Algebra of Combinations

1

6.7

The Binomial Theorem

 

 

 

 

 

 

1

7.1

Functions Defined on General Sets

3

7.2

Application:  Finite-State Automata

1

7.3

One-to-One and Onto, Inverse Functions

1

7.4

Application:  The Pigeonhole Principle

1

7.5

Composition of Functions

3

7.6

Cardinality with Application to Computability

 

 

 

 

3*

8.1

Recursively Defined Sequences

3*

8.2

Solving Recurrence Relations by Iteration

3*

8.3

Second-Order Linear Homogeneous Recurrence Relations

     with Constant Coefficients

3*

8.4

General Recursive Definitions

 

 

 

 

3*

9.1

Real-Valued Functions of a Real Variable and Their Graphs

3*

9.2

O-Notation

3*

9.3

Application:  Efficiency of Algorithms I

3*

9.4

Exponential and Logarithmic Functions:  Graphs and Order

3*

9.5

Application:  Efficiency of Algorithms II

 

 

 

 

1

10.1

Relations on Sets

1

10.2

Reflexivity, Symmetry, and Transitivity

1

10.3

Equivalence Relations

3

10.4

Application:   Simplifying Finite-State Automata

1

10.5

Partial Order Relations

 

 

 

 

1

11.1

Graphs:  An Introduction

1

11.2

Paths and Circuits

1

11.3

Matrix Representation of Graphs

1

11.4

Isomorphisms of Graphs

1

11.5

Trees

1

11.6

Spanning Trees

 

Because of time constraints during an 18 week semester, covering both chapters 8 and 9 is not recommended, but the inclusion of either 8 or 9 is recommended.  Dependent upon the instructor and the makeup of the class, use your judgement as to which one you would like to include.