Devdatt Dubhashi, Rum EDIT:6472, Tel.: (031) 7721046,
dubhashi@chalmers.se
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.
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.
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.
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 |
|
Homework 1
Homework 2 (due latest Jan. 1)
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