CAS CS 591, Algorithmic Techniques for Large Problems, Summer 2014

Class logistics

May 20 – June 27

Lectures in PSY B53, Mon-Thur, 1-3pm.

Instructors

Steve Homer, homer@cs.bu.edu
Office Hours: Wed: 3-4:30

Evimaria Terzi, evimaria@cs.bu.edu
Office Hours: Tues: 3-4:30

Teaching assistants

Dora Erdos, edori@cs.bu.edu
Office Hourse: Thur: 3-4:30

Maryam Ghasemi, ghasemi@cs.bu.edu

Content summary

This course centers on approximation and randomized algorithms that are used to provide approximate solutions to NP-hard problems; problems known to have polynomial-time solutions, and which nevertheless are impractical for large data sets. The course will be built using material from two textbooks:

Although the majority of the course will be based on the material of the above two textbooks, towards the end we will discuss some classical papers that apply some of the techniques covered in the class in practical scenarios, and will test their limits. While we will focus on the theory of approximation algorithms, we will stress those algorithms most useful for large data sets and will in each case, consider the efficiency of modern techniques for carrying out large data-centric computation.

Workload

No late homework will be accepted. You can collaborate to solve the problems (but not in the take home exam), use the web and other available material BUT you should list your collaborators and your references.

In general you need to comply to the academic conduct code.

Prerequisites

The course assumes basic knowledge of Probability (CS 237) and Algorithms (CS 330), or equivalent. Some of the material depends as well on fundamentals of Theory of Computation (CS 332) or equivalent. Acquaintance with this material is helpful as well, though not required for this summer course.

Schedule

Introduction to approximation algorithms: Set Cover
Introduction to randomized algorithms: Min cuts
Knapsack and Bin Packing
k-Cuts and Multicuts
k-median and k-means
k-center and hierarchical clustering
Steiner Trees and TSPs
Graphs as electrical networks
Linear Programming
DNF counting
Counting matchings
Fingerprinting
Semi-definite programming

Homeworks