Important Announcements

Office hours for last week:
- Julia (TTIC 427):
  - Mon March 6, 10:00-11:00
  - Mon March 13, 10:00-12:00
  - Note: there will not be an office hour on Thursday!
- David (Ryerson 162-C):
  - Tue March 7, 3:00-4:00
  - Mon March 13, 1:00-3:00
- Rachit (TTIC library):
  - Wed March 8, 4:00-5:00
- Yuan (Ryerson 254-B):
  - Fri March 10, 3:00-5:00

Practice-Final solving session: will take place Mon March 13, 3:00-5:00 (by Rachit), in the usual classroom.

As a preparation for the final exam, it is highly recommended that you solve the practice final. We'll post a solution on March 12, and Rachit will solve it during an extra problem solving session on March 13.
Homework 4: available here. Due: Tue March 7, noon. Solutions will be published Sun March 12, noon. No submissions will be accepted after that.
Summary of material covered and additional material available here.

Course hours:

Lecture: Tue/Thu 8:50-10:10, at TTIC room 526

Tutorial: Wed 3:00-4:00, at TTIC room 526

Instructor:

Julia Chuzhoy: Office hour: Thu 10:30-11:30, TTIC 427; Email: cjulia@ttic.edu

TA’s:

David Kim (TA in charge): Office hour: Tue 3:00-4:00, Ryerson 162-C; Email: dave.hongk@gmail.com

Yuan Li: Office hour: Fri 3:00-4:00, Ryerson 254-B; Email: yuanli@cs.uchicago.edu

Rachit Nimavat: Office hour: Wed 4:00-5:00, TTIC library; Email: nimavat@ttic.edu

Course Description:

This is a graduate level course on algorithms, with the emphasis on computational problems that are central to both theory and practice, and on developing techniques for the design and the rigorous analysis of algorithms for such problems. In addition to classical results we will discuss several more modern approaches to algorithm design. Course Syllabus with a specific list of topics we plan to cover can be found here.

Text:

The main text is "Algorithm Design" by Kleinberg and Tardos, but not all course material is covered by the book.

Prerequisites:

We will assume that the students are familiar with the following topics, usually covered in undergraduate algorithms courses: time and memory complexity analysis; sorting and searching; basic data structures: linked lists, trees, balanced trees, heaps; algorithmic paradigms: greedy methods, divide and conquer; basic graph and network algorithms: Breadth-First Search, Depth-First Search, Minimum Spanning Tree, shortest path algorithms. This is roughly equivalent to chapters 1-16 and 22-26 of CLRS, excluding the starred sections, or the material covered by the University of Chicago course CMSC 27200. A basic knowledge of probability theory will also be assumed.

Course Requirements:

4 homework assignments (42% in total). See homework policy here.
2-3 short in-class closed-book quizzes (8% in total) – the dates will be announced at least one week in advance
a midterm exam: Feb 14 in class (20%)
a final exam: March 14, 8:00-10:00 (30%)

Useful Links:

Homework policy
Short summary of material covered and plans for the coming lecture/tutorial (will try to keep up to date)
If you have any comments or suggestions about the course, please leave them here (if you leave them without logging into your canvas account they are anonymized)