- 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:25-2: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 |
Non-determinism |
| 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 |
First-order logic, Gödel's theorem. |
|
5/16, 2PM |
Final exam (study guide) |
Office hours schedule (click for location)