# CS 2800 Spring 2020

From CS2800 wiki

Revision as of 12:12, 31 January 2020 by {{GENDER:Mdg39|

'"7This 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

You are responsible for learning the material in the "prep" page **before** the corresponding lecture. The prep page will also contain a link to the previous semester's notes. If you want to look ahead to lectures where I haven't yet posted the prep page, you can visit the CS 2800 Fall 2019 page.

Topic | Date | Lecture Topic |
---|---|---|

Sets and Proof techniques | 1/22 | Introduction (prep, slides) |

1/24 | Set and function definitions (prep, slides) | |

1/27 | Set constructions (prep, slides) | |

1/29 | Proof techniques (prep, slides) | |

Functions and Relations | 1/31 | Function properties (prep, slides) |

2/3 | Injectivity and left inverses (prep) | |

2/5 | Surjectivity and Bijectivity (prep) | |

2/7 | Cardinality (prep) | |

2/10 | Diagonalization (prep) | |

2/12 | Proof techniques review (prep) | |

2/14 | Relations (prep) | |

2/17 | Equivalence classes (prep) | |

Number theory | 2/19 | Induction (prep) |

2/21 | Strong induction and Euclidean division (prep) | |

2/24 | No class; February break | |

Number theory | 2/26 | Base b representation (prep) |

2/28 | GCD algorithm (prep) | |

3/2 | Modular numbers (prep) | |

3/4 | Modular division and exponentiation (prep) | |

3/5 | Prelim 1 | |

Number theory | 3/6 | Euler’s theorem (prep) |

3/9 | Public key cryptography (prep) | |

3/11 | RSA (prep) | |

Category:Automata | 3/13 | Inductively defined sets (prep) |

3/16 | Structural induction (prep) | |

3/18 | Deterministic Finite Automata (prep) | |

3/20 | Automata constructions (prep) | |

3/23 | Unrecognizable languages (prep) | |

3/25 | Non-determinism (prep) | |

3/27 | Regular expressions (prep) | |

3/30 | No class; Spring break | |

4/1 | No class; Spring break | |

4/3 | No class; Spring break | |

Category:Automata | 4/6 | Kleene's theorem (prep) |

Category:Combinatorics | 4/8 | Sum and product rule (prep) |

4/9 | Prelim 2 | |

Category:Combinatorics | 4/10 | Permutations and combinations (prep) |

4/13 | Combinatorial proofs (prep) | |

Category:Probability | 4/15 | Probability spaces (prep) |

4/17 | Conditional probability (prep) | |

4/20 | Random variables (prep) | |

4/22 | Expectation (prep) | |

4/24 | Independent RVs (prep) | |

4/27 | Markov's/Chebychev's/Weak law (prep) | |

Category:Metalogic | 4/29 | Truth tables (prep) |

5/1 | Proof trees (prep) | |

5/4 | Soundness and completeness (prep) | |

TBD | Final exam |

# Office hours schedule

(Click for location)