CS369: Topics in Analysis of Algorithms

(Spring Quarter 2012-2013)

Contact Information

Instructor: Prof. Serge Plotkin

E-mail: plotkin@cs.stanford.edu

Office Phone: 723-0540

Office hours: By appointment

TA: Shayan Ehsani

E-mail: shayane@stanford.edu

Office Hours: Wed 9:00 AM-11:00 AM, Gates B26A

                      Fri   12:00 PM-2:00 PM, Gates B26A

Time and Location

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

Announcements

05/14-Homework 2 is posted!

05/01- Clarifiction on Problem 4, part (a) of Homework 1: Note that this part is exactly like the standard 1/infinity case with only one difference- the loads are computed using scale factors Q_i..

04/25-Today's lecture cancelled.

04/22-Homework 1 is posted!

04/08-We created a Piazza discussion forum for the class, and encourage you to ask questions related to the material or homework on Piazza (rather than via individual emails to a classmate or one of us) – you can even do so anonymously, and LaTeX is supported. Make sure to ask meaningful questions, while being careful not to give away hints on the homework (honor code).
To join: 1) Go to the Piazza website; 2) Type in "Stanford University"; 3) Under Spring 2013 course, find CS 369.

04/04 - Important note: Class attendance is mandatory.

03/22 – Course info

Plan

Tentative, will be updated.

Date	Description
April 2	Intro to Online Algorithms. Paging: offline/online. Marking Algorithm
April 4	Randomized Marking.  Online Steiner Tree
April 9	Steiner tree lower bound. Models for Load Balancing and Scheduling. Identical machines
April 11	Related machines: O(log n) for greedy
April 16	Related machines: log n lower bound for greedy O(1) upper bound
April 18	0/infinity load balancing: lower and upper bounds Yao's min/max theorem and its use for lower bounds
April 23	Unrelated machines: log n upper bound. Applications to online congestion minimization.
April 25	CANCELLED.
May 30	Temporary tasks; Known durations/unrelated: O(log nT) upper bound. Unknown durations/related: O(1) upper bound.
May 2	Robin hood and O(sqrt n) upper bound for 0/infinity with unknown durations
May 7	Throughput-competitive routing
May 9	Online Bipartite Matching Made Simple.(Presenter: Sean Choi)
May 14	Adwords and Generalized On-line Matching.(Presenter: Arpit Goel)
May 16	A Tight Bound on Approximating Arbitrary Metrics by Tree Metrics.(Presenter: Rafael Cosman)
May 21	Buy-at-Bulk Network Design (Presenter: Lucas Garron)
May 23	Online decisions problems/experts Randomized weighted majority
May 28	Efficient algorithms for online decision problems.(Presenter: Alex Churchill)
May 30	Online Convex Programming and Generalized Infinitesimal Gradient Ascent.(Presenter: Jaehyun Park)
June 4	CANCELLED

Handouts

CS261-Notes

Current version of notes. Notes will be updated as we progress in the quarter.

Scribing Slots. Please note that scribing is an integral part of the coursework, and necessary to pass the class. If you’re registered but haven’t yet signed up for scribing please do so by send an email to shayane@stanford.edu. Note that we expect the edited notes one week after the class at the latest.

Homework

Homework 2

Homework 1

Frequently Asked Questions/Course Policies

1. What are the course requirments? Solve 2-3 homework assignments, update 1-2 lecture notes.
2. What is the homework collaboration policy? You are allowed to collaborate with one additional student, but write the solutions on your own. Indicate your collaborator on the first page of every assignment.
3. How will the lecture notes be updated? Each student will update the class lecture notes according to the material covered in 1-2 lectures.
4. Can I e-mail my homework assignments? Yes, please feel free to email your homework in PDF format to cs369-spr1213-staff(at)lists.stanford.edu.
5. What is the late day policy? All assignments are due by end of the lecture on the due date of the homework. You may submit one assignment one "class period" late, i.e., if the due date is on Tuesday you may submit by end of the lecture on Thursday, without penalty. No other extensions will be granted.

Questions?

Staff Mailing List:

cs369-spr1213-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.