Randomized Algorithms, IITMThere 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.
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.
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.
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.
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
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.
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
Date: 5th July 2010
Time: 1:30pm – 4:30pm
Location: BSB-361
Topics covered:
Large Deviation Bounds,
Data stream models
Download Lecture-6 notes
Today’s lecture has been cancelled. The next lecture will be on Monday, 5th July.
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
Randomized Algorithms, IITM 