CS 2800 Spring 2018

From CS2800 wiki

This is the course website for CS 2800, Spring 2018

  • Note on wiki/website: This is our first semester using this software to run the course website. Please let us know of any problems on Piazza.


We are currently migrating the lecture notes to this system. I encourage you to consult last semester's notes for any content that has yet to be migrated.

Images from the review session boards can be found here.

Topic Date Lecture Topic
Sets and proof techniques 1/24 Introduction
1/26 Sets and proofs
1/29 More set notation, induction
1/31 Logical statements, proofs
Functions and relations 2/02 Finish proof techniques, start functions
2/05 Properties of functions
2/07 Function inverses
2/09 Cardinality
2/12 Countability
2/14 Relations (outline)
2/16 Equivalence classes (outline)
2/19 February break — no class
Number Theory 2/21 Euclidean division and strong induction (outline)
2/23 Base b representation (outline)
2/26 Greatest common divisor (outline)
2/28 Modular addition, multiplication, division (outline)
3/02 Snow day
3/05 Modular division (outline)
3/07 Euler's theorem (outline)
exam 3/08 Prelim 1 (Study guide)
3/09 RSA (outline)
Automata Theory 3/12 Inductively defined sets and functions
3/14 Proofs by structural induction (outline)
3/16 Deterministic finite automata (outline)
3/19 Automata constructions (outline)
3/21 Unrecognizable languages (outline)
3/23 Nondeterministic automata (outline)
3/26 Regular expressions (outline)
3/28 Kleene's theorem (outline)
3/30 Kleene's theorem (outline)
4/02 Spring break — no class
4/04 Spring break — no class
4/06 Spring break — no class
Combinatorics 4/09 Sum and product rules, tree diagrams (outline)
4/11 Permutations, quotient rule, combinations (outline)
exam 4/12 Prelim 2 (study guide)
4/13 Combinatoric proofs (outline)
Probability 4/16 Probability introduction and definitions
4/18 Conditional probability
4/20 Independence, definition of Random Variable
4/23 Expectation (outline)
4/25 Variance (outline)
4/27 Markov's and Chebychev's inequalities, weak law of large numbers (outline)
4/31 Hashing (outline)
5/02 Probabilistic Counting (outline)
Metalogic 5/04 Propositional logic formulas and semantics (outline)
5/07 Proofs (outline)
5/09 Soundness and completeness (outline)
exam 5/21 Final exam (Final study guide)

Office hours schedule

(Click for location)