CS7800: Advanced Algorithms
Time & Location:
2:50 - 4:30pm MW, Forsyth Building 236
Staff
Instructor: Jonathan Ullman
Office: 260 West Village H
Office Hours: Tues 3:30-5, Fri 1-2
Teaching Assistant: Mehraneh Liaee
Office: 266 West Village H
Office Hours: M 1-2:30
Updates
- Welcome to CS7800!
- Extra office hours for the first week: Thurs (9/10) 3-5, Fri (9/11) 2-3
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):
- Graph algorithms: shortest path, network flow
- Basic algorithmic paradigms: greedy algorithms, divide-and-conquer, dynamic programming
- Linear programming, convex optimization
- Randomized algorithms
- Learning algorithms
- NP-hardness and approximation algorithms
- Online algorithms
Piazza
This term 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.
Find our class page here
Textbook
We will be using
Algorithm Design by Kleinberg and Tardos. However, we will only follow the textbook loosely, and there will be supplementary readings provided for lectures that cover material from outside of this book.
Many students also find Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein to be a useful reference.
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 typed and submitted by email as a PDF. It is up to you how you want to type your homework, but I recommend using LaTeX (if you're a PhD student, and you're not familiar with LaTeX, you will have to be eventually).
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 the start of class on the due date. To (hopefully) reduce stress, you will have a total of six "late days" that can be used on any problem set, no questions asked. However, you may not use more than two late days on any one assignment. Late days cannot be subdivided. Additional extensions will only be granted in very rare circumstances, so use your late days wisely.
Grading
The final course grade will be computed based on a weighted average of:
- 5-6 problems sets (35% total)
- 2 midterms (30% total)
- a final exam (30%)
- participation in class, in office hours, and on Piazza (5%)