This section contains recitation problems and notes, which include solutions.
REC # | TOPICS | PROBLEMS | NOTES |
---|---|---|---|
1 | Logic, proving an implication | (PDF) | (PDF) |
2 | Induction | (PDF) | (PDF) |
3 | State machines | (PDF) | (PDF) |
4 | Greatest common divisor | (PDF) | (PDF) |
5 | Exponentiation, modular arithmetic, RSA | (PDF) | (PDF) |
6 | Graph basics | (PDF) | (PDF) |
7 | Stable marriage problem | (PDF) | (PDF) |
8 | Build-up error, the grow algorithm | (PDF) | (PDF) |
9 | Traveling salesperson problem | (PDF) | (PDF) |
10 | Analysis of two networks, routing in a Beneš network | (PDF) | (PDF) |
11 | Equivalence relations, chains, topological sort | (PDF) | (PDF) |
12 | The L-tower problem, double sums | (PDF) | (PDF) |
13 | Asymptotic notation, asymptotic equivalence | (PDF) | (PDF) |
14 | Guessing a particular solution, linear recurrences | (PDF) | (PDF) |
15 | Counting problems, pigeonhole principle | (PDF) | (PDF) |
16 | Combinatorial proof, more counting | (PDF) | (PDF) |
17 | Probability, Monty Hall problem | (PDF) | (PDF) |
18 | Total probability law | (PDF) | (PDF) |
19 | Bayes' rule | (PDF) | (PDF) |
20 | Philosophy of probability | (PDF) | (PDF) |
21 | Conditional expectation and total expectation | (PDF) | (PDF) |
22 | Expected value rule for functions of random variables, properties of variance | (PDF) | (PDF) |
23 | Probability theorems | (PDF) | (PDF) |