CS 2800: Discrete Structures

• CMS
• Piazza
• Syllabus
• Schedule
• Office hours

Important information

• Click here for the current semester's website.
• This is the homepage for CS2800 Spring 2016
• Instructors:
  • Professor Michael George. Office hours MW 2:30–3:30 or by appt, Gates 447
  • Professor Joseph Halpern. Office hour: Wednesday 11-12, or by appt., Gates 414
• Class meets Monday, Wednesday, Friday, 1:25-2:15 in Uris G01
• Please read the syllabus

Schedule

(LaTeX) Review

Topic	Date	Lecture summary	Additional material
Basic tools	1/27	Introduction to CS2800
	1/29	Definitions	Assaf Goldberger's "Notes on Proofs" Sam Vandervelde's "Bridge to Higher Mathematics" Rosen, Section 1.7 (Section 1.8 provides supplementary material)
	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-69	Rosen 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/11	Review 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

Office hours schedule (click for location)