The Probabilistic Method - Fall 2011




Contact Information

Schedule

Literature

Program and Examination

Week-by-week Schedule

Homeworks

Some Useful Links


   Contact Information

Lecturer 1 :   Peter Hegarty, Rum MV:L3032, Tel.: (031) 7725371, hegarty@chalmers.se

Lecturer 2 :   Jeff Steif, Rum MV:H5017, Tel.: (031) 7723513, steif@chalmers.se

Lecturer 3 :   Devdatt Dubhashi, Rum EDIT:6472, Tel.: (031) 7721046, dubhashi@chalmers.se


   Schedule

The course will meet for 2 x 45 minutes, twice a week for seven weeks. The times and locations are as follows :

Tuesdays, 13:15 - 15:00, Room MV:F21.

Thursdays, 08:00 - 09:45, Room MV:H12.


   Literature

No textbook is obligatory as the student may take his/her own lecture notes, and most of the material will also be made available online (see the week-by-week schedule below). We do, however, highly recommend the book

(AS) N. Alon and J. Spencer, The Probabilistic Method (3rd edition), Wiley 2008.

Obs! The first two editions of the book also cover all the basic material in this course.

A good book for those particularly interested in CS applications is

(MU) : M. Mitzenmacher and E. Upfal, Probability and Computing : Randomized Algorithms and Probabilistic Analysis, Cambridge University Press 2005.


   Program and Examination

The teaching will involve only lectures , according to the schedule above. Examination will be by means of 2 written homeworks , plus an oral exam in January. To pass the course, one will need to pass the oral exam and attain at least 50% overall. In computing the final grade, 25% will be given to the homeworks and 75% to the exam performance.

Grade thresholds will be computed according to the following schemes :

Chalmers undergraduates: < 50% (U), 50-66% (3), 67-82% (4), 83-100% (5).

GU undergraduates: < 50% (U), 50-74% (G), 75-100% (VG).

PhD students at MV: To pass the course, you must attain the equivalent of a Chalmers 4-grade. i.e.: at least 67%.

PhD students from other departments: Your grade will be computed as for Chalmers undergraduates, at which point it is up to your examiner to determine whether to award you pass or fail.

NOTE: Students are allowed to collaborate on homeworks, but each person must write and hand in their own solutions and indicate with whom they have collaborated.


   Week-by-week Schedule

As we proceed, completed material will be marked in green. The files of lecture notes will be updated as the course proceeds, and should eventually include most, if not all, of the course content. Students will be informed if anything ends up not being included in these notes. We recommend that you take your own lecture notes if you want to be certain of not missing anything.

OBS! The following schedule is approximate and will be continuously updated.

Week Stuff Lecture Notes
44 The Basic Probabilistic Method

Applications in CS : Satisfiability of clauses.

Applications in GT : Ramsey numbers, Turan's theorem and independent sets.

Applications in NT : Van der Waerden numbers.

PDF

Supplement
45 Basic method (ctd.)

Further applications : Turan's theorem (ctd.), Sum-free sets (NT), Shannon's theorem (CS), Local coloring (GT), Girth and chromatic number (GT).

PDF
46 First Moment Method : Markov's inequality.

Second Moment Method : Chebyshev's inequality.

Applications in NT : Number of subset sums, number of prime divisors.

CS Interlude : The probabilistic method in design of algorithms.

Application : Min-cut in a graph.

PDF
47 Second moment method (ctd.)

Applications in GT : Subgraph threshold, Clique numbers of random graphs.

Applications in CS : Quicksort, median finding.

PDF
48 Chernoff bounds.

Application in CS : Routing in networks.

PDF
49 Chernoff bounds (ctd.)

Applications in NT : Thin bases, discrepancy theory*.

Application in GT : Degrees in random graphs*.

Martingale methods : Azuma's inequality.

* In lecture notes only, not presented in class and therefore optional material.

PDF
50 Martingale methods (ctd.)

Application in GT : chromatic numbers of random graphs.

A final CS application of Chernoff bounds : Dimension reduction.

Some background material

1 2

See also handout from Chapter 7 of [AS]
11-27/01 Oral exam. Each student should book a time at the following doodle  


   Homeworks

Homework 1

Homework 2 (due latest Jan. 1)


   Some Useful Links



Om du har kommentarer, påpekanden eller annat att säga om kursen, tryck   här

Peter Hegarty <hegarty@math.chalmers.se>
Last modified: Tue Dec 20 14:31:00 CET 2011