CS369F: Topics in Analysis of Algorithms

(Spring Quarter 2008-2009)

Contact Information
Instructor: Prof. Serge Plotkin
E-mail: plotkin@cs.stanford.edu
Office Phone: 723-0540
Office hours: By appointment

TA: Rohan Jain
E-mail: rohanj@stanford.edu
Office Hours: Tuesdays 3-4 pm and Fridays 11-12 pm in Gates B24B
 
Time and Location

Tuesday -Thursday 11AM - 12:15PM
Gates, Room 260
Announcements

06/01 -- There would be no class on Tuesday 06/02. Thanks for a great class!
05/24 -- An FAQ section is up. Please have a look at it for announcements regarding homework 2.
05/19 -- Homework 2 is out! Available in the Handouts section. Due on Thursday, May 28.
04/23 -- Homework 1 is out! Available in the Handouts section. Due on Tuesday, May 5.
04/14 -- There would be no class on Thursday. See you all next week!
04/14 -- Notes for lectures will be available in the Handouts section. They will be updated every week with new material.
04/01 -- Course information now available in the Handouts section
04/01 -- New and updated webpage is up and running!
04/01 -- There are no TA office hours this week. In case you have a query, please email the TA and we will try and respond as soon as possible.


Topics Covered (under construction)

Week #
Description
Reading
1
Introduction to course, Paging problem Pages 1-3
2
Steiner Trees Pages 4-7
3
Load Balancing Pages 8-12
4
Load Balancing, the one infinity case Pages 13-15
5
Yao Minimax, Unrelated Machines, Application to Routing Pages 14-22
6
Online Load balancing of temporary tasks, Multicommodity flows Pages 23-29
7
Congestion Model of Multicommodity flows, Paper on Adwords presented by Bahman Bahmani Pages 30-32, Paper
8
Paper on Bartals approximation for HST's presented by Shaddin Dughmi Paper
8
Paper on Online Convex programming and gradient descent presented by Justin Lebar Paper
9
Kalai Vempala's paper on online decision problems presented by Justin Solomon Paper, Notes


Handouts

Latest Notes - Updated every week (PDF)
Homework 2 (PDF)
Homework 1 (PDF)
Course Information (PDF)

FAQ

For Homework 2, In Question 4 the costs are postive integers
For Homework 2, In Question 3 assume all profits are 1

Questions?

Staff Mailing List: cs369f-spr0809-staff(at)lists.stanford.edu
If you take the course for credit, you will automatically be subscribed to a class mailing list. If you are auditing, please contact the TA or the professor.