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