WEEK |
DATE |
ANNOUNCEMENTS |
TOPIC & READING |
LAB |
1 | Aug 31 | | Course Introduction slides | Lab 1, lab1.tex |
Sep 02 | | Probability Theory Basics slides |
Sep 04 | | Probability Theory Basics (cont'd)
slides |
2 | Sep 07 | | Independence, Random Variables
slides |
|
Sep 09 | | Random Variables slides |
Sep 11 | Drop/Add ends | Asymptotic Analysis
slides |
3 | Sep 14 | no class -- Rosh Hashanah | Asymptotic Analysis(continued)
Wednesday Friday slides. Notes on Asymptotic Properties | Lab 2 |
Sep 16 | |
Sep 18 | |
4 | Sep 21 | | The basic Probabilistic Method, Ramsey Theory
slides |
|
Sep 23 | class/lab cancelled -- Yom Kippur
Exam 1 (Sep 24)
| The basic Probablistic Method
|
Sep 25 | |
5 | Sep 28 | | Linearity of Expectation
slides | Lab 3, lab3.tex |
Sep 30 | | Linearity of Expectation
- Alon/Spencer 2.3-2.5
- Shoup Appendix A.1
Wednesday Friday slides. |
Oct 02 | |
6 | Oct 05 | | Variance
slides | Lab 4, lab4.tex |
Oct 07 | | Inequalities and Tail Bounds Wednesday Friday slides. |
Oct 09 | |
| Oct 12 | Fall Break |
Oct 14 |
Oct 16 |
7 | Oct 19 | | Alterations slides | Lab 5, lab5.tex |
Oct 21 | | Alterations slides |
Oct 23 | | Alterations slides |
8 | Oct 26 | | The Second Moment Method slides |
|
Oct 28 | Exam 2 | The Second Moment Method slides |
Oct 30 | | The Second Moment Method slides |
9 | Nov 02 | | Applications: Random Graphs Monday Wednesday slides. | Lab 6 |
Nov 04 | |
Nov 06 | |
10 | Nov 09 | | More Applications Monday Wednesday Friday slides. |
|
Nov 11 | |
Nov 13 | |
11 | Nov 16 | | Randomized Algorithms Monday Wednesday Friday slides. | Lab 7 |
Nov 18 | |
Nov 20 | |
12 | Nov 23 | | P, NP, NP-Completeness Monday Wednesday |
|
Nov 25 | |
Nov 27 | Thanksgiving |
13 | Nov 30 | | P, NP, NP-Completeness (continued) Monday Wednesday slides. |
|
Dec 02 | Exam 3 |
Dec 04 | |
14 | Dec 07 | | Course Wrapup |
|