CS 361B:  Advanced Algorithms, Spring 2014

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



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







CS261 Notes (from Spring 2014)








CS361B Lecture Notes



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

Tentative schedule



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.



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