| 1 |
Aug 19 |
Introduction; Rules of Sum and Product |
1.1 |
- |
- |
HW1 posted. |
| 2 |
Aug 24 |
Rule of Product; Permutations |
1.1,1.2 |
- |
- |
HW2 posted. |
| 3 |
Aug 26 |
Rule of Product; Permutations |
1.1,1.2 |
pdf |
pdf |
HW1 due. Quiz 1 in class. |
| 4 |
Aug 31 |
Combinations |
1.3 |
- |
- |
HW2 due. HW3 posted. |
| 5 |
Sep 2 |
Poker Hands |
1.3 |
pdf |
pdf |
Quiz 2 in class. |
| 6 |
Sep 7 |
Binomial Theorem; Pascal's Triangle |
1.3 |
- |
- |
HW3 due. HW4 posted. |
| 7 |
Sep 9 |
Stars and Bars Model |
1.4 |
pdf |
pdf |
Quiz 3 in class. |
| 8 |
Sep 14 |
Set Theory |
3.1 |
- |
- |
HW4 due. HW5 posted. |
| 9 |
Sep 16 |
Test 1: Classes 1 through 7; 1.1-1.4 |
- |
pdf |
pdf |
- |
| 10 |
Sep 21 |
Tuples; Cartesian Product; Countable Sets |
- |
- |
- |
HW5 due. HW6 posted. |
| 11 |
Sep 23 |
Countability; Cantor's Diagonalization Argument |
3.2 |
pdf |
pdf |
Quiz 5 in class. |
| 12 |
Sep 28 |
Cantor's Diagonalization Consequences; Probability Theory |
3.4,3.5 |
- |
- |
HW6 due. HW7 posted. |
| 13 |
Sep 30 |
Probability Theory II |
3.5 |
pdf |
pdf |
Quiz 6 in class. |
| 14 |
Oct 5 |
Conditional Probability |
3.6 |
- |
- |
HW7 due. HW8 posted. |
| - |
Oct 7 |
No Class: Fall Recess |
- |
- |
- |
- |
| 15 |
Oct 12 |
Conditional Probability Rule; Prosecutor's Fallacy; Languages |
3.6; S 1.1 |
- |
- |
HW8 due. HW9 posted. |
| 16 |
Oct 14 |
Languages and Recursive Definitions |
S 1.1,1.2 |
pdf |
pdf |
Quiz 8 in class. |
| 17 |
Oct 19 |
Deterministic Finite Automata I |
S 1.2 |
- |
- |
HW9 due. HW10 posted. |
| 18 |
Oct 21 |
Test 2: Classes 8--16 and HW 5--9 |
- |
pdf |
pdf |
Test 2 in class. |
| 19 |
Oct 26 |
Deterministic Finite Automata II |
- |
- |
- |
HW10 due. HW11 posted. |
| 20 |
Oct 28 |
Nondeterministic Finite Automata |
- |
pdf |
pdf |
Quiz 10 in class. |
| 21 |
Nov 2 |
NFA to DFA Conversion |
- |
- |
- |
HW11 due. HW12 posted. |
| 22 |
Nov 7 |
NFA to DFA Conversion Example; Concatenation of Languages |
11.1 |
pdf |
pdf |
Quiz 11 in class. |
| 23 |
Nov 9 |
NFA Application: 4-corners game |
- |
- |
- |
HW12 due. HW13 posted.
|
| 24 |
Nov 11 |
Introduction: Graph Theory |
- |
pdf |
pdf |
Quiz 12 in class. |
| 25 |
Nov 16 |
Graphs II |
11.1 |
- |
- |
HW13 due. |
| 26 |
Nov 18 |
Test 3: Classes 17 to 24, HW10--HW13 |
- |
T3 |
T3-soln |
- |
| 27 |
Nov 30 |
Graph Isomorphism; Planar graphs; Euler's formula |
11.2,11.4 |
- |
- |
- |
| 28 |
Dec 2 |
Hypercubes; Degree-Sum Formula; Networks |
- |
Q14 |
Q14-soln |
HW14 due; Quiz 14 in class. HW15 assigned. |
| 29 |
Dec 7 |
Network Flows; Matchings |
13.3,13.4 |
- |
- |
- |
| 30 |
Dec 9 |
Stable Matchings; Gale--Shapley Algorithm |
- |
- |
- |
HW15 due. |
| - |
Dec 17 |
Final Exam: Fri Dec 17, 8am-10am |
- |
- |
- |
- |