- 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

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 |