CS 573 Graduate Algorithms, Fall 2011

Lectures: Tue & Thur 12:30pm to 1:45pm in 1109 Siebel Center


Instructor: Chandra Chekuri (chekuri@cs.illinois.edu), 3228 Siebel Center
Office hours: Mon 10-11am and Fri 11am-noon, in the open area near 3303 in Siebel Center
Administrative assistant: Elaine Wilson, 3229 Siebel Center

Teaching assistant: Ben Moseley (bmosele2@illinois.edu)
On-Campus Office hours: Mondays 1-2pm, in the open area near 3303 in Siebel Center.
Online Offices hours: Thursdays 6-7pm CST.

Course information:

Schedule and lecture notes

Course topics: Below is a list of high-level topics that we hope to cover. This list is tentative.

  • Divide and conquer, FFT
  • (Advanced) Dynamic Programming
  • Shortest path algorithms and negative cycle detection
  • Randomization in algorithms and data structures
  • Network flows and applications, minimum-cost flow (?)
  • Non-bipartite graph matching (?)
  • Introduction to linear programming
  • NP-Completeness and reductions
  • Basics of approximation and online algorithms

Announcements

  • Homework 6 is for you to practice. The latex file.
  • Homework 5 is due on Tuesday, November 29th in class. The latex file.
  • Homework 4 is due on Tuesday, November 1st in class. The latex file.
  • Homework 3 is due on Tuesday, October 18th in class. The latex file.
  • Midterm 1 is on Thursday, September 29th. The exam for on-campus students is in 101 Transportation Building from 7-9pm.
  • Homework 2 is due on Tuesday, September 27th in class. The latex file.
  • Homework 1 is due on Tuesday, September 13th in class. The latex file.
  • Homework 0 is due in class Tuesday, August 30th.
  • The class is full, but if you are still interested in taking it this semester, don't panic!
    Note: Course webpages are borrowed extensively (with gratitude and permission) from Jeff Erickson's Fall 2010 version of CS 573.