COMP 382: Reasoning about Algorithms: Fall 2016

*[This page is only a "brochure" for the
course. All course material is available on Canvas.]*

Writing algorithms is fun, but how do you show that your algorithm behaves correctly on all possible inputs? Can you estimate your algorithm's worst-case runtime? Is it possible that there is no efficient algorithm for the computing task that you are trying to solve? To answer these questions, you have to mathematically reason about algorithms.

COMP 382 is an intermediate-level algorithms class with an emphasis on such mathematical reasoning. The class teaches you many new algorithm design techniques, for example advanced dynamic programming, greedy optimization, randomized algorithms, and reduction to problems like linear programming. Along with these, you learn proof principles that you can use to show that a given algorithm behaves correctly and efficiently, or that certain algorithmic problems are unlikely to have efficient solutions.

The class is organized in two sections. Lectures for the two sessions are held together on Tuesdays and Thursdays, 10:50am-12:05pm, at HRZ 210. Labs are held at HUM 117. The lab for Section 002 is from 4:00pm-5:15pm on Thursdays, and the lab for Section 003 is from 5:30pm-6:45pm on Thursdays.

Policies for the class are available here.

We will make heavy use of the Canvas and Piazza systems for this course. Specifically, all course announcements, assignments, lecture slides, and solutions will be made available through Canvas. We will also use Canvas to receive soft copies of assignment submissions. We will use Piazza to answer questions about the class.

Office Hours (also by appointment) | |||
---|---|---|---|

Instructors | |||

Swarat Chaudhuri | Wednesdays 3-4pm | Duncan Hall 3103 | |

Michael Burke | Tuesdays 3:00-4:00pm | Duncan Hall 3134 | |

Teaching assistants | |||

Suguman Bansal | Mondays 11am-12pm | DH 3063 | |

Arkabandhu Chowdhury | Mondays 1-2pm | DH 3097 | |

Ryan Spring | Wednesdays 10am-11am | DH 3076 | |

Lucas Tabajara | Wednesdays 1pm-2pm | DH 3053 | |

Dan Ye | Mondays 2-3pm | DH 3117 | |

Marc Canby | Wednesdays 8-9pm | McMurtry Commons | |

Max Hasbrouck | Sundays 4-5pm | Will Rice Commons | |

Krishna Thiagarajan | Tuesdays 4-5pm | TBD | |

Hunter Tidwell | TBD | TBD | |

Anthony Tzen | Wednesday 7-8pm | McMurtry Commons | |

Susan Wen | Thursdays 1-2pm | Martel Commons |

The class doesn't have an official textbook. We will use material from the following two texts, among others:

- Algorithm Design, Jon Kleinberg and Eva Tardos.
- Algorithms, Jeff Erickson, based on notes for his Algorithms course at UIUC.