CIS 11: Course Outline

Text - Discrete Mathematics 5th ed.

by - K. Ross & C. Wright (Prentice Hall)

Weeks 1 & 2: Sets, Sequences, and Functions

Set Operations; Functions; Inverses of Functions; Sequences.

          H.W. - Chapter 1:

                    1.3 - 1, 3, 5, 9, 11, 13 (Special Sets)

                    1.4 - 1, 3, 5, 7, 11, 13 (Set Operations)

                    1.5 - 1, 3, 5, 7, 8, 13 (Functions)

                    1.6 - 1, 3, 5, 7, 9 (Sequences)

                    1.7 - 1, 3, 5, 7, 11 (Properties of Functions)

Weeks 3 & 4: Elementary Logic

Propositional Calculus; Methods of Proof; Analysis of Arguments.

          H.W. - Chapter 2:

                    2.1 - 1, 9, 15 (Introduction)

                    2.2 - 1, 3, 5, 7, 9, 19 (Propositional Calculus)

                    2.3 - 5, 7, 9, 13 ((Proofs)

                    2.4 - 1, 3 (Methods of Prooofs)

                    2.5 - 1, 3, 7, 9, 17 (Logic in Proofs)

                    2.6 - 1, 5, 9a,c, 13 (Analysis of Arguments)

Examination #1:

Weeks 5 & 6: Relations

Relations; Digraphs and Graphs; Matrices; Equivalence Relations and Partitions.

          H.W. - Chapter 3:

                    3.1 - 1, 3, 9, 11, 13 (Relations)

                    3.2 - 1, 3, 9, 10, 11, 15 (Digraohs and Graphs)

                    3.3 - 3, 5, 11, 15 (Matrices)

                    11.3 - 1, 7, 11 (Multiplication of Matrices)

                    3.4 - 1, 5, 7, 13, 15 (Equivalence Relations and Partitions)

                    3.5 - 1, 3, 5, 15 (The Division Algorithm and integers Mod p)

Weeks 7 & 8: Induction and Recursion

Loop Invariants; Mathematical Induction; Recursive Definitions; Recurrence Relations.

          H.W. - Chapter 4:

                    4.1 - 9, 11, 17, 19, 21 (Loop Invariants)

                    4.2 - 1, 5, 7, 13, 17, 19 (Mathematical Induction)

                    4.4 - 1, 3, 7, 9, 17 (Recursive Definitions)

                    4.5 - 1, 3, 7, 11, 15 (Recurrence Relations)

                    4.6 - 1, 7, 11, 13 (More Induction)

Weeks 9 & 10: Counting

Basic Counting Techniques; Elementary Probability; Inclusion-Exclusion Principle; Binomial Methods; Counting and Partitions; Independence; Bayes Formula.

          H.W. - Chapter 5

                    5.1 - 1, 3, 7, 9, 11, 15 (Basic Counting Techniques)

                    5.2 - 1, 3, 5, 7, 9, 15, 19 (Elementary Probability)

                    5.3 - 1, 3, 7, 9, 15, 17 (Inclusion-Exclusion and Binomial Methods)

                    5.4 - 1, 3, 5, 9, 11 (Counting and Partitions)

                    9.1 - 1, 3, 7, 9, 13, 17, 19 (Independence in Probabilty and Bayes Formula)

Examination #2:

Weeks 11 & 12: Boolean Algebra

Boolean Algebras; Boolean Expressions; Logic Networks; Karnaugh Maps: Isomorphism.

          H.W. - Chapter 10:

                    10.1 - 5, 7 (Boolean Algebra)

                    10.2 - 1, 3, 7 (Boolean Expressions)

                    10.3 - 1, 3 (Logic Networks)

                    10.4 - 1, 5, 7, 9 (Karnaugh Maps)

                    10.5 - 1, 3, 5 (Isomorphism)

Weeks 13 & 14: Introduction to Graphs and Trees

Graphs; Edge Traversal Problems; Trees; Rooted Trees; Vertex Traversal Problems; Minimum Spanning Trees.

          H.W. - Chapter 6:

                    6.1 -

                    6.2 -

                    6.3 -

                    6.4 -

                    6.5 -

                    6.6 -

Final Examination:

Notes:

Solutions to the homework problems for each chapter are available in the back of the text (see pg. 538).