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

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

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

(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

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).

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

Applications in CS :
Satisfiability of clauses.
Applications in GT : Ramsey numbers, Turan's theorem and
independent sets.
Applications in NT : Van der Waerden numbers.
Further applications : Turan's theorem (ctd.), Sum-free sets (NT), Shannon's theorem (CS), Local coloring (GT), Girth and chromatic number (GT).
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.
Applications in GT : Subgraph threshold, Clique numbers of random graphs.
Applications in CS : Quicksort, median finding.
Application in CS : Routing in networks.
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.
Application in GT : chromatic numbers of random graphs.
A final CS application of Chernoff bounds : Dimension reduction.
See also handout from Chapter 7 of [AS]

Week
Stuff
Lecture Notes
44
The Basic Probabilistic Method
PDF
45
Basic method (ctd.)
PDF
46
First Moment Method : Markov's inequality.
PDF
47
Second moment method (ctd.)
PDF
48
Chernoff bounds.
PDF
49
Chernoff bounds (ctd.)
PDF
50
Martingale methods (ctd.)
Some background material
11-27/01
Oral exam. Each student should book a time at the following
doodle

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