CS7800: Advanced Algorithms

Syllabus

Schedule

Assignments

Time & Location:

3:25 - 5:05pm TF, 310 Hurtig
Note: Please note that the room has changed to 310 Hurtig!

Staff

Instructor: Jonathan Ullman
    Office: 623 ISEC
    Office Hours: Tue 11-12

Teaching Assistant: Albert Cheu
    Office: ISEC 6th Floor
    Office Hours: Thu 1-2 in ISEC 605

Updates

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):

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 for Piazza.

Textbook

We will be using Algorithm Design by Kleinberg and Tardos. There will be some 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 concepts from discrete math that are relevant to algorithms.

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. In my experience, comfort with mathematical reasoning and proofs is more important than familiarity with algorithms. If you are unsure about your background, please come talk to me in the first week of the course.

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 earth and you have to pilot a space shuttle 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: Both the midterm and final exam will be "in class" (i.e. not take home)