CS 2800: Discrete Structures

Important information

Schedule

+ intro to number theory e ,
Topic Date Lecture summary Reading
Basic tools 8/24 L1: Introduction to CS2800
8/26 L2: Precision and clarity Syllabus, MCS Chapter 1
8/29 L3: Functions MCS Chapter 4 (4.2 optional)
8/31 L4: Cardinality MCS Chapter 8.1
Induction 9/2 L5: Basic induction proofs (slides 1-15) MCS Chapter 5.1
9/7 L6: Induction and well ordering, slides 16-30 MCS Chapter 2.1-2.3
9/9 L7: Strong induction+ faulty induction proofs, slides 31-43 MCS Chapter 5.2
9/12 L8: Inductive Definitions + Puzzles, slides 44-54 no reading!
Combinatorics 9/14 L9: Sum Rule; Product Rule, slides 1-13 MCS 15.1-3
9/16 L10: Division Rule; Permutations and Combinations, slides 14-36 MCS 15.4-7
9/19 L11: Binomial Theorem Combinatorial Proofs, slides 37-50 MCS 15.10
9/21 L12: Inclusion-Exclusion Rule; Balls and Urns, slides 51-69 MCS 15.9
9/23 L13: Balls and Urns, Pigeonhole Principle, slides 70-85 MCS 15.8
Probability 9/26 L14: Intro to probability, slides 1-28 MCS 17.5, 18.4.6
9/28 L15: Conditional probability, slides 29-54MCS 18.2
9/30 L16: Tree diagrams, independence, slides 55-72 MCS 17.1-17.3 (17.4 optional)
10/3 L17: Bayes' Rule, law of total probability, random variables; see also slides k73-90 MCS 18.4-18.5, 18.7-18.8, 19.1 (18.6, 18.9 optional, but interesting!)
10/5 L18: distributions + expected value, slides 91-104 MCS 19.2-19.3.2, 19.3.4-19.4.5 (19.4.6, 19.4.7 optional, but fun!)
10/7 L19: Linearity of expectation + the power of randomization, slides 105-128 MCS 19.3.3, 19.5-19.5.3
10/12 L20: Variance, standard deviation, Markov + Chebyshev Inequality, slides 129-139MCS 20.1, 20.2, 20.3.1
Number Theory 10/14 L21: Division and base b MCS 9.1 (no quiz)
10/17 L22: GCD (notes from spring) MCS 9.2, 9.4
10/19 L23: Numbers mod m (notes from spring) MCS 9.6,9.7
10/21 L24: Modular division, exponentiation MCS 9.9
10/24 L25: Euler's theorem MCS 9.10
10/26 L26: RSA MCS 9.11
Automata 10/28 L27: Automata intro (spring notes) MCS 6.1 (No quiz)
10/31 L28: Structural induction, automata constructions MCS 7.1, 7.3, 7.5; Automata constructions 1.1
11/2 L29: Non-determinism (spring) Pass and Tseng 8.2
11/4 L30: Regular expressions (spring) Pass and Tseng 8.3
11/7 L31: Kleene's Theorem (spring) Automata constructions 1.3
11/9 L32: Non-computability (spring) Pass and Tseng "Limits of DFA"
Logic 11/11 L33: Propositional logic, slides 1-14 MCS 3.1-3.3
11/14 L34: Tautologies and proofs, slides 15-28MCS 3.3 (optional: 3.5)
11/16 L35: First-order logic, Godel's Theorem, slides 29-40 MCS 3.6
Graph Theory
11/18 L36: Graph theory: basic definitions, handshaking theorem, graph isomorphism; slides 1-14 MCS 10.1,12.1-12.4
11/21 L37: Graph theory: Eulerian paths, graphs and scheduling; slides 15-29 MCS 10.5.1, 10.5.2
11/28 L38: Graph theory: graph coloring,bipartite graphs, matching; slides 30-40 MCS 12.5, 12.6
11/30 L39: Graph theory: reflexive, symmetric, and transitive relations, partial orders; slides 41-50 MCS 10.6, 10.8, 10.10
Exams 9/27 Prelim 1 Study guide
10/27 Prelim 2 Study guide
12/12 9 AM: Final exam Study guide

Office hours schedule (click for location)