CS7800: Advanced Algorithms
Time & Location:
3:25 - 5:05pm TF, 310 Hurtig
Note: Please note that the room has changed to 310 Hurtig!
Instructor: Jonathan Ullman
Office: 623 ISEC
Office Hours: Tue 11-12
Office: ISEC 6th Floor
Office Hours: Thu 1-2 in ISEC 605
- Welcome to CS7800!
- Please note that the class has been moved to 310 Hurtig!
- Please sign up for the course on Piazza by following this link.
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
- Approximation algorithms
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 firstname.lastname@example.org
Please use this link to sign up for Piazza.
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.
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.
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.
The final course grade will be computed based on a weighted average of:
- weekly homework assignments (40%)
- midterm exam (20%)
- final exam (35%)
- participation in class and on Piazza (5%)
Both the midterm and final exam will be "in class" (i.e. not take home)