CS7800: Advanced Algorithms

Syllabus

Time & Location:

1:35 - 3:15pm TF, Ryder Hall 153

Staff

Instructor: Jonathan Ullman
    Office: 260 West Village H
    Office Hours: Tue 3:15-5, also by appointment.

Teaching Assistant: Mehraneh Liaee
    Office: 266 West Village H
    Office Hours: Mon 10:30-12 in 166 WVH

Updates

Welcome to CS7800!
I will have extra office hours during the first few weeks of classes: Fri 9/9 3:15-5, Mon 9/12 3-5, Wed 9/14 10-12.

Overview

This course is about advanced techniques for design and analysis of algorithms. I will try to emphasize some of the breadth and diversity of algorithms research. Potential topics include (but are not limited to):

Basic algorithmic paradigms: greedy algorithms, divide-and-conquer, dynamic programming
Combinatorial optimization
Linear programming and convex optimization
NP-hardness and approximation algorithms
Randomized algorithms
Online algorithms

Piazza

We will be using Piazza for class discussion. The system will make it possible to get help quickly and and efficiently from classmates, the TA, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com.

Please use this link to sign up.

Textbook

We will be using Algorithm Design by Kleinberg and Tardos. There will be supplementary readings provided for lectures that cover material from outside of this book. Any edition of the book is fine, as I will not be assigning homework problems straight from the book.

Many students also find Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein or Algorithms, Etc. by Jeff Erickson to be useful references for algorithms and Mathematics for Computer Science by Lehman, Leighton, and Meyer to be a useful review of discrete math concepts.

Prerequisites

This is a PhD core course; if you are not a PhD student in the college, then you need to get approval from me to enroll. The course will be fast-paced and will cover a number of advanced topics in algorithms over the 13-week period. If you have at least some familiarity with the material in the textbook (especially the early chapters), and are comfortable with the mathematical background, then you are well prepared. Otherwise you should come talk to me.

Homework Policies

All homework solutions must be typeset in LaTeX and submitted by email with both PDF and LaTeX source. I will provide the source file for HW assignments to help you get started.

I encourage you to talk through the solutions to homework problems with your classmates, although I recommend trying to solve all the problems yourself first. If you do collaborate with other students, you must write up all your solutions by yourself (do not share written solutions) and you must list all of your collaborators on your submitted homework.

Problem sets are to be submitted by midnight on the due date. No extensions will be granted, except in very rare and extreme circumstances (e.g. your house was sucked into a Poltergeist the night before the assignment was due or an asteroid is approaching the early and you have to pilot a space shuttle into its center to blow it up before it destroys life as we know it). However, your lowest HW grade will not count towards your final grade.

Grading

The final course grade will be computed based on a weighted average of:

5 problems sets (50% total)
midterm (20%)
a final exam (25%)
participation in class, in office hours, and on Piazza (5%)