Overview

This is an advanced course in algorithms aimed at Ph.D. students in computer science and related fields. The course surveys fundamental topics like optimization—greedy algorithms, dynamic programming, network flow, and linear and convex programming—randomized algorithms, online algorithms, NP-completeness. The course emphasizes how to reason and communicate rigorously about algorithms.

Time & Location

TF 1:35 – 3:15pm in Snell Library 115

Instructor

Teaching Assistants

Course Content

This course will cover a number of advanced topics in algorithms that are chosen to make students aware of important algorithmic tools, introduce rigorous algorithmic thinking, and to highlight some important applications of algorithms in the real world. In particular, we will cover topics like:

• Optimization
• Greedy algorithms
• Dynamic programming
• Network flow
• Linear programming
• Convex optimization and gradient descent
• Reductions
• Applications of network flow
• NP-completeness
• Randomized algorithms
• Hashing and load balancing
• Nearest neighbor search
• Sublinear algorithms
• Advanced topics (time permitting) such as
• Stable matching
• Approximation algorithms
• Online algorithms
• Linear algebraic algorithms
• Coding theory
• Auction theory

Prerequisites

This is a fast-paced course covering a number of advanced topics in algorithms. If you are not a PhD student in Khoury, then you need to receive approval from the instructor to enroll. If you have taken a solid undergraduate course in algorithms, and are comfortable with mathematical reasoning and communication, then you are well prepared. Comfort with mathematical reasoning is far more important than specific background material. Because this is a PhD course it is expected that everyone will have slightly different background, and you may need to fill in some gaps in your knowledge. The first homework assignment, given in the first week, will help you identify these gaps and assess your preparation for the course. If you're unsure about your background, please come talk to me during the first week of the course.

Lectures

People learn in different ways, but in my opinion coming to lectures is the best way to learn the course material, and I expect that students will attend and be engaged in lectures. However, I will not take attendance, and I trust students to decide when they need to miss lectures due to illness or other personal or professional priorities.

Lectures will be done on an iPad with a mix of pre-made and hand-drawn slides. They will not be recorded, however I will post the slides before lecture so you can follow along and after lecture so you can see the annotations.

Textbook

We will primarily use the textbook Algorithm Design by Kleinberg and Tardos, although there will be supplementary readings on certain topics. I encourage you to be resourceful about finding a copy of the textbook, and please let me know if you'd like help aquiring the textbook.

Many students also find the free book Algorithms by Jeff Erickson to be helpful for getting an alternative view of the material, and the free book Mathematics for Computer Science by Lehman, Leighton, and Meyer to be useful for reviewing mathematical concepts.

Discussions

We will be using Piazza for course discussions. This system makes it easy for you to get help quickly and efficiently from the instructor, TA, or your classmates. If you have general questions about the course material or logistics, please use Piazza and make your questions public so that other students with the same questions can see the answers. If you have questions about the material that are specific to you—for example you want to know if a certain aspect of your solution is correct, without giving away the solution to others—you can use private messages to the instructors rather than email to help us stay organized. If you have logistical questions or personal questions—for example you are sick, traveling, or an asteroid destroyed your homework—you can use private messages to the instructors or email the instructors directly.

Homework

We will have 6 homework assignments throughout the semester assigned every two weeks. Homework assignments will be entirely mathematical, involving designing algorithms and analyzing their properties.

• Homework must be typed in LaTeX. I will provide the source files to help you get started.
• Homework must be submitted on Gradescope. Sign up with entry code K33NED

The course runs much more smoothly when students turn in work on time. However, we know that conflicts and unusual circumstances arise, so you will have a supply of late days to allocate throughout the semester.

• You will be given 6 total late days for the course.
• You may use a maximum of 2 late days on any one assignment, so that we can release solutions in a timely fashion.
• Further extensions will be given only in rare circumstances, at the instructor's discretion.

If you're like me, you will have more fun and learn more if you discuss the homework problems with your classmates. However, there are a few rules you must adhere to.

• You must write up all solutions by yourself, and may not share any written solutions.
• You may have a maximum of two collaborators per assignment.
• You must list all your collaborators on your submission.
• Collaboration is transitive—if you list a collaborator, they must list you.

Template created by Kira Goldner©