Lecture on 3rd August

There will be a lecture by Prof. C.Pandu Rangan on 3rd August.

Time: 11:30 – 13:00hrs
Location: CS-36
Agenda: The lecture will begin with a reinforcement of incremental design and backward analysis and then proceed to discuss another important basic paradigm of randomized algorithms – randomized attrition.  We will discuss some generic strategy to analyse such algorithms using chernoff bounds.

Download Lecture-12 notes.

Lecture 11

Date: 26th July 2010

Time: 1:30pm – 4:30pm

Location: BSB-361

Topics covered: Extending Moser-Tardos, Randomized rounding and derandomization, Revisit of network flows,  Lenstra-Shmoys-Tardos and related results..

Download Lecture-11 notes.

Lecture 11

The final lecture in the series will be on Monday, 26th July. Details:

Part1:
Time: 11a.m-12 noon
Location: BSB-361, IITM

Part2:
Time: 13:30 – 16:30
Location: BSB-361, IITM

All are welcome.

Special lecture – July 9th

Prof. C.Pandu Rangan will be giving a special lecture on randomized algorithms today(9th July) at 1:30p.m (for about 1 to 1.5hrs). All interested students are welcome to attend.

Time: 1:30pm – 3:00pm

Location: BSB-361

Topic covered: Randomized incremental approach.

Download RandomizedIncrementalApproach Notes

Prof. Aravind is not available today, he will deliver another lecture later this month. The details of which will be put up in advance.

Lecture 9

Date: 8th July 2010

Morning lecture:

Time: 10:00am – 11:00am

Location: BSB-361

Topics covered: Proof of Lovasz local lemma, Asymmetric Lovasz local lemma, Moser-Tardos (statement).

Download lecture notes for the morning class here.

Afternoon lecture:

Time: 1:30pm – 4:30pm

Location: BSB-361

Topics covered: k-SAT hypergraph 2-colouring.

Download lecture notes for the afternoon class here

Lecture 8

Date: 7th July 2010

Time: 1:30pm – 4:30pm

Location: BSB-361

Topics covered: Edge colouring, Martingale’s tail inequality, Packet routing, Lovasz Local lemma (introduction).

Download Lecture-8 notes.

Lecture 7

Date: 6th July 2010

Time: 1:30pm – 4:30pm

Location: BSB-361

Topics covered:

Data stream models, probabilistic random constructions, Randomness extractors, Resource allocation.

Download Lecture-7 notes

Lecture 6

Date: 5th July 2010

Time: 1:30pm – 4:30pm

Location: BSB-361

Topics covered:
Large Deviation  Bounds,
Data stream models

Download Lecture-6 notes

No lecture on 2nd July.

Today’s lecture has been cancelled. The next lecture will be on Monday, 5th July.

Lecture 5

Date: 1st July 2010

Time: 1:30pm – 4:30pm

Location: BSB-361

Topics covered:
The method of conditional probabilities, kth moment method,
Normal Distribution and Poisson Distribution in Discrete contexts,
Chernoff bounds and its variants.

Download Lecture-5 notes

Follow

Get every new post delivered to your Inbox.