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