 This is the homepage for CS2800 Spring 2017. The Fall 2017
website is here.
 Instructor: Michael George. Office hours WF 2:30–3:30 in Uris 494 or by appointment in Gates 447
 Class meets Monday, Wednesday, Friday, 1:252:15 in Uris G01
 The course text is "Mathematics for Computer Science" (version dated 9/28/2016).
 Please read the syllabus
Schedule
For upcoming lectures, I encourage you to consult the
corresponding sections of last
semester's lecture notes.
Topic  Date  Lecture topic 
Basics 
1/25 
Introduction 
1/27 
Modeling problems 
1/30 
Quantifiers and proofs 
Functions and relations 
2/1 
Functions, inverses, 'jectivity 
2/3 
Cardinality 
2/6 
Relations 
2/8 
Equivalence classes 
2/10 
Combinatorics 
2/13 
Constructing reals 
2/15 
Induction 
2/17 
Combinatorics II 
Probability 
2/22 
Probability spaces 
2/24 
Conditional probability 
2/27 
Random variables 
2/29 
Combining random variables 
3/3 
Variance, probability bounds 
3/6 
Chebychev's inequality, Weak law of large numbers 
3/8 
Proof techniques review 

3/9 
7:30–9:00PM Prelim 1 (study guide) 

3/10 
Probabilistic counting 
Automata 
3/13 
Inductive definitions 
3/17 
Structural induction 
3/20 
Finite automata 
3/22 
Automata constructions 
3/24 
Pumping lemma 
3/27 
Nondeterminism 
3/29 
Regular expressions 
3/31 
Kleene's theorem 
4/10 
Turing machines 

4/13 
7:30–9:00PM Prelim 2 (study guide) 
Number theory 
4/12 
Euclidean division 
4/14 
Strong induction, number bases 
4/17 
Euclid's GCD algorithm, modular numbers 
4/19 
Modular addition, multiplication, division 
4/21 
Modular exponentiation, Euler's theorem 
4/24 
RSA 
Graphs 
4/26 
Basic definitions, handshaking theorem 
4/28 
Eulerian and Hamiltonian circuits 
5/1 
Coloring 
Formal logic 
5/3 
Propositional logic 
5/5 
Proofs 
5/8 
Soundness and completeness 
5/10 
Firstorder logic, Gödel's theorem. 

5/16, 2PM 
Final exam (study guide) 
Office hours schedule (click for location)