# CS 2800: Discrete Structures CMS Piazza Syllabus Schedule Office hours

## Important information

• This is the homepage for CS2800 Spring 2016
• Instructors:
• Class meets Monday, Wednesday, Friday, 1:25-2:15 in Uris G01

## Schedule

(LaTeX) Review
Topic Date Lecture summary Additional material
Basic tools 1/27 Introduction to CS2800
1/29 Definitions
2/1 Functions Rosen, Section 2.3.
2/3 Cardinality Rosen, Section 2.5.
Induction
2/5 Induction slides; we covered slides 1-20. Rosen, Section 5.1
2/8 Induction slides; we covered slides 21-30. Rosen, Section 5.2
2/10 Induction slides; we covered slides 31-45. Rosen, Section 5.2
2/12 Induction slides; we covered slides 49-57 (I didn't cover slides 46-48, but I left them in). Rosen, Section 5.3
Number Theory 2/17 The muddy children puzzle + number theory: number theory slides Rosen, Section 4.1
2/19 Number bases Rosen, Section 4.2
2/22 Euclid's GCD algorithm Rosen, Section 4.3
2/24 Modular arithmetic Rosen, Section 4.3
2/26 Modular division, exponentiation
2/29 Euler's theorem
3/2 RSA Rosen, Section 4.6
3/4 RSA, number theory magic; intro to combinatorics; Combinatorics slides; we covered slides 1-4. Rosen, Section 4.6, pp. 385-389
Combinatorics 3/7 Combinatorics slides; we covered slides 5-31 (Sum rule + product rule, permutations and combinations). Rosen, pp. 391-395; Sec. 6.3
3/9 Combinatorics slides; we covered slides 32-48 (Combinatorial Identities + Pascal's triangle) Rosen, Section 6.4
3/11 Combinatorics slides; we covered slides 49-62 (Balls and urns, Binomial Theorem) Rosen, Section 6.5
3/14 Combinatorics slides; we covered slides 63-74 (Pigenohole principle) + slides 1-7 on probability (what is probability?) Rosen, Section 6.2
Probability 3/16 Probability slides; we covered slides 8-26 (properties of probability + conditioning) Rosen, Sections 7.1, 7.2
3/18 Probability slides; we covered slides 27-43
3/21 Probability; we covered slides 44-52 Rosen, Section 7.3
3/23 Probability; we covered slides 53-69Rosen Section 7.4
3/25 Probability; we covered slides 70-89.
4/4 Probability; we covered slides 90-103 + slides 1-4 of graph theory
Graph Theory 4/6 Graph theory; we covered slides 5-17 Rosen, Sections 9.1 and 10.1
4/8 Graph theory; we covered slides 18-33 (parts of) Rosen, Sections 10.2-10.4
4/11 Graph theory
4/13 Relations, start of automata
Automata 4/15 Designing automata, structural induction
4/18 Language of a machine Automata constructions, Rosen, Section 13.3
4/20 Non-determinism Rosen, Section 13.3
4/22 Regular expressions Rosen, Section 13.4
4/25 Converting between NFA and RE Rosen, Section 13.4
4/27 Pumping lemma
Logic 4/29 Propositional logic Pass and Tseng, Section 6.1; Rosen, Sections 1.1-1.3
5/2 Proof systems Table of inference rules; Pass and Tseng, Section 6.2; Rosen, Section 1.6
5/4 Soundness and completeness
5/6 First-order logic; we covered slides 1-22 Pass and Tseng, Section 6.3; Rosen, Section 1.4
5/9 Fun topics: slides 23-40. Godel's theorem, 8 powerful ideas from the course, random graphs, and NP-completeness
Review 5/11Review session
Prelims + Exam 3/10 Prelim I, See piazza for locations Study guide
4/14 Prelim II, location TBA Study guide
5/16, 2PM Final exam Study guide