|
|
CS 361B: |
[Announcements]
[Notes and
Handouts] [Frequently Asked Questions] [Homework]
[Course
Information]
·
May 1, 2012: No class this Thursday (May 3). Scribe slots
have been adjusted accordingly.
·
May 1, 2012: Homework #2 posted, it is due by Thursday May
10.
·
April 18, 2012: Scribing guidelines updated.
·
April 16, 2012: 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 email.
·
April 12, 2012: Some guidelines for scribing now posted.
·
April 10, 2012: Homework #1 posted, it is due by Thursday
April 19.
·
April 10, 2012: Regular office hours today canceled, for an
alternative time this week please make an appointment by email.
·
April 5, 2012: Updated lecture notes and assignment to
scribing slots have been posted.
·
April 4, 2012: Classroom change – starting Thursday April 5
we will meet at room 380-380X.
·
March 27, 2012: 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 2012 courses, find CS 361B.
·
March 27, 2012: Welcome to the CS 361B website!
|
Handout
Title |
Format |
Updated |
Comment |
||||
|
Scribing
Guidelines |
|
|
|
04/18/2012 |
|
|
|
|
Scribing
Slots |
|
|
|
04/05/2012 |
|
|
|
|
CS261
Notes |
|
|
|
04/05/2012 |
|
|
|
|
Lecture
Notes |
05/23/2012 |
These
notes are work in progress and will be updated over the length of the
quarter. |
|||||
1. What
are the course requirements? Solve 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 cs361b-spr1112-staff@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.
|
Course
Information |
Topics: Fundamental techniques used in the design and analysis of
exact and approximate algorithms for combinatorial optimization problems.
Examples of such problems include generalized flow, multi-commodity flow,
sparsest cut, generalized Steiner trees, load balancing, and scheduling.
Emphasis on linear programming and duality; interior point methods for LP; and
strongly-polynomial algorithms.
Lectures: 3 units, Tue, Thu 11:00
AM – 12:15 PM at 110-114.
Prerequisites (recommended): CS 261, or equivalent.
Textbooks: There are no required textbooks for the class – the lecture
notes on this website are a comprehensive collection of the
material. For further reference
see
·
Vazirani, “Approximation
Algorithms”, 2004.
·
Hochbaum “Approximation
Algorithms for NP-Hard Problems”, 1996.
·
Ahuja, Magnanti and Orlin,
“Network Flows: Theory, Algorithms and Applications”, 1993.
· Grotschel, Lovasz and Schrijver, “The Ellipsoid Method and Combinatorial Optimization”, 1988.
E-mail: Please use the following e-mail address, which is forwarded
to the instructor and TA – cs361b-spr1112-staff@lists.stanford.edu.
|
Instructor: Prof. Serge Plotkin E-mail: plotkin@cs.stanford.edu Office hours: Tue 1:30 PM –
3:00 PM Office location: Gates 472 Office phone: (650)
723-0540 |
Teaching
Assistant:
Inbal Talgam-Cohen E-mail: italgam@stanford.edu
Office hours: Mon 10:00 AM – 12:00 PM Office location: Gates 466 |
Information
for Students with Documented Disabilities:
Students who have a disability which may necessitate an academic accommodation
or the use of auxiliary aids and services in a class, must initiate the request
with the Student Disability Resource Center (SDRC), located within the Office
of Accessible Education (OAE). The SDRC will evaluate the request with required
documentation, recommend appropriate accommodations, and prepare a verification
letter dated in the current academic term in which the request is being made.
Please contact the SDRC as soon as possible; timely notice is needed to arrange
for appropriate accommodations. The Office of Accessible Education is located
at 563 Salvatierra Walk (phone: 723-1066; TDD: 725-1067).
CS
361B Spring 2012
Please send comments and suggestions to cs361b-spr1112-staff@lists.stanford.edu.