CS 361B:  Advanced Algorithms, Spring 2014


     [Announcements]   [Notes and Handouts]   [Frequently Asked Questions]   [Homework]   [Course Information]      


Announcements

 

Homework #3 posted!

Homework #2 posted!

Homework #1 posted!

Class webpage on Piazza: piazza.com/stanford/spring2014/cs361b.

March 24, 2014: Welcome to the CS 361B website!

Notes & Handouts

 

 

Handout Title

 

Format

 

Updated

 

Comment

CS261 Notes (from Spring 2014)

 

PDF

 

 

3/22/3014

 

 

CS361B Lecture Notes

PDF

4/10/2014

These notes are work in progress and will be updated over the length of the quarter.

Tentative schedule

PDF

3/22/2014

The schedule will be periodically updated.

 

Frequently Asked Questions / Course Policies

Homework Assignments

 

·         Homework 3 (PDF)

·         Homework 2 (PDF)

·         Homework 1 (PDF)

 

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 Hewlett Teaching Center 102.

 

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-spr1314-staff@lists.stanford.edu.

 

Instructor:

Prof. Serge Plotkin

E-mail: plotkin@cs.stanford.edu

Office hours: Thu 1:00 PM – 2:30 PM and by appointment

Office location: Gates 472

 

Teaching Assistant:

Shayan Ehsani

E-mail: shayane@stanford.edu

Office hours: Fri 10:30 AM - 12:30 PM

Office location: Gates B24A

 

 

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 2014
Please send comments and suggestions to cs361b-spr1314-staff@lists.stanford.edu