| 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-54 | MCS 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-139 | MCS 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-28 | MCS 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
|