Syllabus
Readings refer to the course text: Kenneth Rosen, Discrete Mathematics and Its Applications, 7th Edition, McGraw-Hill, 2012. ISBN 0-073-38309-0.
Topics and schedule are subject to change.
Lecture Schedule
| DATE | LECTURE/EVENT | NOTES/READINGS |
|---|---|---|
| 8/28 | Welcome and Introduction | |
| 8/30 | Propositional Logic and Applications | 1.1-2 |
| 9/2 | No class — Labor Day | |
| 9/4 | Propositional Equivalences | 1.3 |
| 9/6 | Predicates and Quantifiers | 1.4-5 |
| 9/9 | Homework 1 due | |
| 9/9 | Rules of Inference | 1.6 |
| 9/11 | Proof Methods and Strategies | 1.7-8 |
| 9/13 | Sets, Set Operations, Functions | 2.1-3 |
| 9/16 | Sequences and Summations, Cardinality of Sets | 2.4-5 |
| 9/18 | Homework 2 due | |
| 9/18 | Relations | 9.1, 9.3 |
| 9/20 | Closures of Relations, Equivalence Relations, Partial Orders | 9.4-6 |
| 9/23 | Divisibility and Modular Arithmetic, Integer Representations | 4.1-2 |
| 9/25 | Primes and GCD | 4.3 |
| 9/27 | Solving Congruences | 4.4 |
| 9/30 | Homework 3 due | |
| 9/30 | Mathematical Induction | 5.1 |
| 10/2 | Strong Induction and Well-Ordering | 5.2 |
| 10/4 | Recursive Definitions and Structural Induction | 5.3 |
| 10/7 | Cryptography | 4.6 |
| 10/9 | Prelim 1 Review – §1, 2.1-5, 4.1-4, 5.1-3, 9.1, 9.3-6 | Review sheet |
| 10/11 | Prelim 1 | |
| 10/14 | Fall Break | |
| 10/16 | Counting, Pigeonhole Principle | 6.1-2 |
| 10/18 | Homework 4 due | |
| 10/18 | Permutations and Combinations, Binomial Coefficients | 6.3-4 |
| 10/21 | Generalized Permutations | 6.5 |
| 10/23 | Introduction to Discrete Probability | 7.1 |
| 10/25 | Probability Theory | 7.2 |
| 10/28 | Bayes' Theorem | 7.3 |
| 10/30 | Homework 5 due | |
| 10/30 | Expectation and Variance | 7.4 |
| 11/1 | Recurrence Relations, Solving Linear Recurrences | 8.1-2 |
| 11/4 | Generating Functions | 8.4 |
| 11/6 | Inclusion-Exclusion and Applications | 8.5-6 |
| 11/8 | Homework 6 due | |
| 11/8 | Prelim 2 Review – §6.1-6.5, 7.1-7.4, 8.1-8.2, 8.4-8.6 | Review sheet |
| 11/11 | Prelim 2 | |
| 11/13 | Graphs and Graph Models, Graph Terminology | 10.1-2 |
| 11/15 | Graph Isomorphism and Graph Connectivity | 10.3-4 |
| 11/18 | Euler and Hamilton Paths, Shortest Path Problems | 10.5-6 |
| 11/20 | Languages and Grammars | 13.1 |
| 11/22 | Homework 7 due | |
| 11/22 | Finite-State Machines | 13.2 |
| 11/25 | Nondeterministic Automata and the Subset Construction | 13.3 |
| 11/27–29 | Thanksgiving Recess | |
| 12/2 | Regular Expressions and Kleene's Theorem | 13.4 |
| 12/4 | Construction of Regular Expressions | Handout |
| 12/6 | State Minimization | Handout |
| 12/6 | Homework 8 due | |
| 12/16 | Final exam review, 7–9pm, Olin 155 – §10.1-6, 13.1-4 | Review sheet |
| 12/19 | Final Exam, 9–11:30am (exam period Q), Barton Hall West-Main Floor |