CME 323: Distributed Algorithms and Optimization

Spring 2016, Stanford University
Mon, Wed 1:30 PM - 2:50 PM at Braun Lecture Hall, Mudd Chemistry Building

Instructor: Reza Zadeh

The emergence of large distributed clusters of commodity machines has brought with it a slew of new algorithms and tools. Many fields such as Machine Learning and Optimization have adapted their algorithms to handle such clusters. The class will cover widely used distributed algorithms in academia and industry.

The course will begin with an introduction to fundamentals of parallel and distributed runtime analysis. Afterwards, we will cover distributed algorithms for:

  • Convex Optimization
  • Matrix Factorization
  • Machine Learning
  • Neural Networks
  • Numerical Linear Algebra
  • Large Graph analysis
  • Streaming algorithms

Class Format

We will focus on the analysis of parallelism and distribution costs of algorithms. Sometimes, topics will be illustrated with hands-on exercises using Apache Spark.

Pre-requisites: Targeting graduate students having taken Algorithms at the level of CME 305 or CS 261. Being able to competently program in any main-stream high level language. There will be homeworks, a midterm, one scribed lecture, and a project.

Grade Breakdown:
Homeworks and scribing: 40%
Midterm: 30%
Project: 30%

The midterm will be Monday May 2nd in class

Required textbook: Parallel Algorithms by Guy E. Blelloch and Bruce M. Maggs [BB]

Optional textbooks:
Models of Computation by John E. Savage [S]
Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein [CLRS]
Learning Spark by Holden Karau, Andy Konwinski, Patrick Wendell, Matei Zaharia [KKWZ]
Convex Optimization by Boyd and Vandenberghe [BV]
Algorithm Design, by Kleinberg and Tardos [KT]

Homework

Homework 1 [pdf] [tex] Due April 11th. [Solution]

Homework 2 [pdf] [tex] Due April 27th. [Solution]

Homework 3 [pdf] [tex] Due May 18th. [Solution]

Homework 4 [pdf] [tex] Due May 25th.

Scribe template

Lectures and References

Previous Years

Spring 2015: [class webpage]

Supplementary Materials

Advanced Data Science on Spark: [slides]

Spark Intro Tutorial: [slides] [code and data - 1 GB]

Spark Devops Slides: Spark Summit slides

Contact

Reza: rezab at stanford
Office hours: by appointment

TA

Andreas Santucci: santucci at stanford
Office hours: Tuesdays 3:15 pm - 5:15 pm

Nolan Skochdopole: naskoch at stanford
Office hours: Mondays, 3:15 pm - 5:15 pm

TA office hours will be held in the Huang Engineering Center basement (in front of the ICME office)