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:

Administrivia:Audience, prerequisites, reading material, etc.- Stuff you already (should) know
Course policies:Homework • Grading • Academic integrity • I2CS- Grades (on Compass)

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 classTuesday, August 30th.

- Please read the course policies on homework, grading, and especially academic integrity.
- LaTeX source
- You may find Jeff Erickson's notes on induction and solving recurrences useful.
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.