CS 2800: Discrete Structures

• CMS
• Piazza
• Syllabus
• Schedule
• Office hours

Important information

• Click here for the current semester
• This is the homepage for CS2800 Fall 2015
• Instructors:
  • Professor Michael George. Office hours MWF 2:30–3:30 or by appt, Gates 447
  • Professor John Hopcroft.
• Class meets Monday, Wednesday, Friday, 1:25-2:15 in Uris G01
• Please read the syllabus

Schedule

Topic	Date	Lecture summary	Additional material
Basic tools	8/26	Introduction to CS2800, Functions
	8/28	Creating definitions	Assaf Goldberger's "Notes on Proofs" Sam Vandervelde's "Bridge to Higher Mathematics"
Cardinality	8/31	Cardinality
	9/2	Countability	Proof that |A| = |B|
	9/4	Uncountable sets, halting problem
Functions	9/9	Inverses	Facts about inverses
	9/11	Relations
Probability	9/14	Probability definitions	Peter Cameron's Notes on Probability
	9/16	Probability
	9/18	Probability
	9/21	Markov and Chebychev
	9/23	Law of large numbers
	9/25	Random graphs
	9/28	Random algorithms
Prelim	9/30	Logic review
	10/2	Prelim 1	Study guide
Number theory	10/5	Bases and division
	10/7	Strong induction, Euclid's algorithm	Adam Bjorndahl's Puzzles and Paradoxes in induction U. of Toronto induction problems
	10/9	Congruence mod m
	10/12	No class (enjoy your break!)
Regular languages	10/14	Regular expressions
	10/16	Finite automata	Automata constructions (LaTeX)
	10/19	Nondeterminism
	10/21	NFA = DFA = RE
Modular arithmetic	10/23	Equivalence classes
	10/26	Modular arithmetic
	10/28	Euler's theorem
	10/30	RSA
Prelim	11/2	Prelim 2	Study guide
	11/4	RSA Example
	11/6	Signing, prelim review
	11/9	Structural induction
More automata	11/11	Pumping lemma	Hopcroft and Ullman. Introduction to Automata Theory, Languages, and Computation
	11/13	Context free grammars
	11/16	Turing machines
	11/18	Recursive sets
	11/20	Halting problem
	11/23	NP completeness
		Happy thanksgiving!
Logic	11/30	Propositional logic	Pass and Tseng, Ch. 6 List of inference rules
	12/2
	12/4
Future	12/17	9:00 AM, Final	Study guide

Office hours schedule