COMP 382: Reasoning about Algorithms: Fall 2016

Instructors: Swarat Chaudhuri and Michael Burke

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


Course description

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.

Lectures and Labs

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

Policies for the class are available here.

Canvas and Piazza

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.

People

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

Texts

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