| 1 |
Aug 22 |
Introduction; Rules of Sum and Product |
1.1 |
- |
- |
- |
| 2 |
Aug 27 |
Permutations |
1.2 |
- |
- |
HW1 posted. |
| 3 |
Aug 29 |
Combinations |
1.3 |
- |
- |
- |
| 4 |
Sep 3 |
Poker Hands; Sigma Notation |
1.3 |
- |
- |
HW1 due. HW2 posted. |
| 5 |
Sep 5 |
Binomial Theorem; Pascal's Triangle |
1.3 |
Q1 |
Q1-soln |
Quiz 1 in class. |
| 6 |
Sep 10 |
Stars and Bars Model |
1.4 |
- |
- |
HW2 due. HW3 posted. |
| 7 |
Sep 12 |
Set Theory |
3.1 |
Q2 |
Q2-soln |
Quiz 2 in class. |
| 8 |
Sep 17 |
Set Theory II; Powerset; Test 1 Review |
3.1 |
- |
- |
HW3 due. HW4 posted. |
| 9 |
Sep 19 |
Test 1 |
- |
T1 |
T1-soln |
Test 1 in class. |
| 10 |
Sep 24 |
Cartesian Product; Countability; Russel's Paradox |
3.2 |
- |
- |
HW4 due. HW5 posted. |
| 11 |
Sep 26 |
Cantor's Diagonalization Argument |
- |
Q4 |
Q4-soln |
Quiz 4 in class. |
| 12 |
Oct 1 |
Russel's Paradox; Probability Theory |
3.4,3.5 |
- |
- |
HW5 due. HW6 posted. |
| 13 |
Oct 3 |
Probability Theory II: Independence |
3.6 |
Q5 |
Q5-soln |
Quiz 5 in class. |
| 14 |
Oct 8 |
Probability Examples; Birthday Paradox |
3.5,3.6 |
- |
- |
HW6 due. HW7 posted. |
| - |
Oct 10 |
No Class: Fall Break |
- |
- |
- |
(No Quiz 6.) |
| 15 |
Oct 15 |
Languages, Automata |
Ch 6; S 1.1 |
- |
- |
HW7 due. Note: S is Sipser, Intro. to Theory of Computation |
| 16 |
Oct 17 |
Test 2: Lectures 7--14 and HW 4--7 |
- |
T2 |
T2-soln |
Test 2 in class. HW8 posted. |
| 17 |
Oct 22 |
Deterministic Finite Automata I |
S 1.2 |
- |
- |
HW8 due. HW9 posted. |
| 18 |
Oct 24 |
DFA's II |
S 1.2 |
Q8 |
Q8-soln |
Quiz 8 in class. |
| 19 |
Oct 29 |
Nondeterministic Finite Automata |
- |
- |
- |
HW9 due. HW10 posted. |
| 20 |
Oct 31 |
NFA to DFA |
- |
Q9 |
Q9-soln |
Quiz 9 in class. |
| 21 |
Nov 5 |
NFA to DFA Examples; Concatenation of languages |
- |
- |
- |
HW10 due. |
| 22 |
Nov 7 |
NFA application: 4 corners |
11.1 |
Q10 |
Q10-soln |
Quiz 10 in class. HW11 posted. |
| 23 |
Nov 12 |
Review Test 3 |
- |
- |
- |
HW11 due.
|
| 24 |
Nov. 14 |
Test 3: Lectures 15--22 and HW 8--11 |
- |
T3 |
T3-soln |
Test 3 in class. |
| 25 |
Nov 19 |
Intro to Graphs |
11.1 |
- |
- |
HW12 posted. |
| 26 |
Nov 21 |
Intro to Graphs II |
11.2,11.3 |
- |
- |
- |
| 27 |
Dec 3 |
Planar graphs; Euler's formula |
11.4 |
- |
- |
HW 12 due. |
| 28 |
Dec 5 |
Planar graph edge bound; Network flows |
11.4, 13.3 |
Q12 |
Q12-soln |
Quiz 12 in class. HW13 assigned. |
| 29 |
Dec 10 |
Network cuts; max-flow/min-cut theorem; matchings |
13.3,13.4 |
- |
- |
- |
| 30 |
Dec 12 |
Stable Matchings; Gale--Shapley Algorithm |
- |
- |
- |
HW13 due. |
| - |
Dec 20 |
Final Exam: Fri Dec 20, 11am-1pm |
- |
- |
- |
- |