CS 2800 Spring 2020

This is the course website for CS 2800, Spring 2020.

• Instructor: Michael George. Office hours TBD.

• Class meets Monday, Wednesday, Friday, 10:10-11:00am in Statler 185
• Please read the syllabus
• Please enroll in Piazza for all course announcements and discussion
• Homework is posted on Piazza
• Be sure to frequently refer to the list of Useful pages

Schedule

Topic	Date	Lecture Topic
Sets and Proof techniques	1/22	Introduction
	1/24	Set and function definitions
	1/27	Set constructions
Sets and Proof techniques	1/29	Proof techniques
Functions and Relations	1/31	Function properties
	2/3	Injectivity and left inverses
	Functions and Relations	2/5	Surjectivity and Bijectivity
2/7		Cardinality
2/10		Diagonalization
Functions and Relations	2/12	Proof techniques review
Functions and Relations	2/14	Relations
	2/17	Equivalence classes
Number theory	2/19	Induction
	2/21	Strong induction and Euclidean division
	2/24	No class;
Number theory	2/26	Base b representation
	Number theory	2/28	GCD algorithm
3/2		Modular numbers
3/4		Modular division and exponentiation
	3/5
Number theory	3/6	Euler’s theorem
	3/9	Public key cryptography
Number theory	3/11	RSA
Category:Automata	3/13	Inductively defined sets
	3/16	Structural induction
Category:Automata	3/18	Deterministic Finite Automata
	3/20	Automata constructions
Category:Automata	3/23	Unrecognizable languages
Category:Automata	3/25	Non-determinism
	3/27	Regular expressions
	3/30	No class;
	4/1	No class;
	4/3	No class;
Category:Automata	4/6	Kleene's theorem
Category:Combinatorics	4/8	Sum and product rule
	4/9
Category:Combinatorics	4/10	Permutations and combinations
	4/13	Combinatorial proofs
Category:Probability	4/15	Probability spaces
	4/17	Conditional probability
	4/20	Random variables
Category:Probability	4/22	Expectation
Category:Probability	4/24	Independent RVs
	4/27	Markov's/Chebychev's/Weak law
Category:Metalogic	4/29	Truth tables
	5/1	Proof trees
Category:Metalogic	5/4	Soundness and completeness
	TBD

Office hours schedule

(Click for location)