CS 2800 F13 Syllabus
Skip to main content



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