The Probabilistic Method

Announcements

  • A tar file containing a sample paper in tex format is here. See the Final Project writeup for instructions on how to access/use this file.
  • Solution sketches to problems from Lab 7 are here.
  • Exam 3 will be in lab on Wednesday December 2. As with Exam 2, you are allowed to bring one double-sided hand-written sheet of notes.
  • Specifications for the Final Project have been posted.

Schedule

This syllabus is a living document; please be aware that many elements on this page will change throughout the semester, including the course schedule.

It is your responsability to review this page weekly for updates.

WEEK   DATE   ANNOUNCEMENTS TOPIC & READING LAB
1

Aug 31

  Course Introduction
slides
Lab 1, lab1.tex

Sep 02

  Probability Theory Basics
  • Shoup 8.1
slides

Sep 04

  Probability Theory Basics (cont'd)
  • Shoup 8.2

slides
2

Sep 07

  Independence, Random Variables
  • Shoup 8.3

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
  • Alon/Spencer 1.1

slides

Sep 23

class/lab cancelled -- Yom Kippur


Exam 1 (Sep 24)

The basic Probablistic Method

Sep 25

 
5

Sep 28

  Linearity of Expectation
  • Shoup 8.4

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
  • Shoup 8.4

slides
Lab 4, lab4.tex

Oct 07

  Inequalities and Tail Bounds
  • Shoup 8.5

Wednesday Friday slides.

Oct 09

 
 

Oct 12

Fall Break

Oct 14

Oct 16

7

Oct 19

  Alterations
  • Alon/Spencer 3.1, 3.2
slides
Lab 5, lab5.tex

Oct 21

  Alterations
  • Alon/Spencer 3.3
slides

Oct 23

  Alterations
  • Alon/Spencer 3.5
slides
8

Oct 26

  The Second Moment Method
  • Alon/Spencer 4.1, 4.2
slides

Oct 28

Exam 2

The Second Moment Method
  • Alon/Spencer 4.3,4.4
slides

Oct 30

  The Second Moment Method
  • Alon/Spencer 4.4,4.5
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