CS 5150/6150 -- Advanced Algorithms
Jump to
class schedule, or
homeworks.
Course Outline
This course will cover the fundamentals of algorithm design, one of the most important aspects of computing. We will discuss some basic paradigms, with an emphasis on mathematically reasoning about the correctness and complexity of algorithms. The course requires a knowledge of UG-level data structures and algorithms, as well as basic graph theory and probability. Most importantly, you need to be comfortable understanding and coming up with mathematical proofs.
A rough set of topics we will cover is the following:
- Overview of divide and conquer, greedy algorithms and local search, and dynamic programming
- Randomization in algorithm design
- Optimization and linear programming formulation of problems
- Limits of efficient algorithms: NP completeness, hardness of approximation
- Other models: online algorithms, distributed computation
The focus will be on how to design algorithms for new problems, and on how to reason about the "performance" of an algorithm. Performance, based on the context, can refer to the space/time complexity, the approximation guarantee, the run-time in a distributed model, or a combination of these measures. In short, the goal is to give a taste of algorithm design, and the kind of questions we care about.
Prerequisites
As most first year MS/PhD students are expected to take this class, there are no enforced pre-reqs. However, a knowledge of basic data structures, graph theory, calculus, and probability will be assumed. To get a sense of what I mean, take a look at chapters 1-6 here. It is also crucial to be comfortable with reading and designing mathematical proofs. A good place to brush up on your math background is the monograph of Lehman and Leighton (chapters 1, 2, 3, 6, 12, 18, 20, 21, 22). Also, take a look at HW0. This is an optional HW, but the problems are meant to give a sense of the background needed. If any of the problems takes over half an hour for you to solve, consider discussing with the instructor.
Programming?
The course is about designing and reasoning about algorithms. We will not explicitly do any implementation, but you should be able to (at least roughly) implement any algorithm we cover. The course project will involve implementation. Any instructor-approved programming language can be used for the project.
Logistics
Time : 10:45 am - 12:05 pm, Tuesday and Thursday
Location : WEB L105
Instructor and Office Hours
- Name: Aditya Bhaskara, MEB 3470
- Contact: bhaskara.course AT gmail DOT com
- Office hours: 1:00 pm - 2:00 pm, Tuesday and Friday.
TAs and office hours
For the TA office hours (+locations) please check the canvas page.
To send email to the TAs, please use this address: utah-algo-ta@googlegroups.com
Exams and grading
The homeworks (see below) will count for 60% of the final grade (best five out of six will be considered). The exam and project will each count for 20%. This will be used to obtain a total score. Grading will be based on a combination of this score and the score in the exam.
Exam: we will have one examination for the course. The date/time of this exam are set by the university, available here. It will be on Tuesday, December 11, 2018, 10:30 am - 12:30 pm.
Textbooks and references
There is no single textbook for the course, so the lecture slides/videos and the lecture notes will be important references. Apart from these, the following notes/textbooks are all excellent references for different portions of the class. The first three are standard algorithms textbooks. They cover all the topics we will see in the first half of the course (and a lot more).
- J. Kleinberg, E. Tardos. Algorithm Design.
- T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms.
- S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms.
- Lecture notes by Jeff Erickson (at UIUC -- an excellent set of notes, and many cool exercises).
- R. Motwani, P. Raghavan. Randomized Algorithms.
- C. Moore, S. Mertens. Nature of Computation. If I have to recommend one textbook for learning about algorithms and computation, it's this.
Course schedule
Here is the tentative schedule for the course. We will post links to lecture videos, slides and notes as the semester progresses.
- Week 1 (August 21, 23). Topics: Introduction, course overview, basic review.
Lecture 1: Introduction to the course, logistics, and basics of writing algorithms and proofs.
Lecture 2: Basic data structures. Another example of correctness proofs.
- Week 2 (August 28, 30). Topics: Divide and conquer, analyzing recurrences, overview of dynamic programming.
Lecture 3: Divide and conquer algorithms. Writing and solving recurrences.
Lecture 4: Divide and conquer (continued). Introduction to dynamic programming. Here is a link to lecture notes about the linear time median problem (with details of the algorithm we outlined in class).
- Week 3 (September 4, 6). Topics: Dynamic programming (continued), greedy algorithms.
Lecture 5: Dynamic programming: subset sum, knapsack, traveling salesman problem. Here is a story about the origin of the name dynamic programming.
Lecture 6: Dynamic programming (continued), greedy algorithms.
- Week 4 (September 11, 13). Topics: Greedy algorithms, local search, gradient descent.
Lecture 7: Greedy algorithms (continued): spanning tree, max k-cover.
Lecture 8: Local search, gradient descent.
- Week 5 (September 18, 20). Topics: Gradient descent, basic graph algorithms
Lecture 9: Local search (continued), Intro to graph algorithms
Lecture 10: Shortest paths (continued).
- Week 6 (September 25, 27). Topics: Flows and cuts
Lecture 11: Course review, introduction to flows/cuts
Lecture 12: Flow-cut duality, Ford-Fulkerson algorithm
- Week 7 (October 2, 4). Topics: Conclude flows, start randomized algorithms
Lecture 13: Applications of flows. Basic randomized algorithms
Lecture 14: Expected running time, quick sort, Markov's inequality
*** FALL BREAK ***
- Week 8 (October 16, 18). Randomized algorithms (continued)
Lecture 15: Balls and bins -- illustrating Markov's inequality, linearity of expectation, union bound
Lecture 16: Estimation via sampling, Chernoff bound
- Week 9 (Oct 23/25): Conclude randomized algorithms, formulating problems as optimization.
- Week 10 (Oct 23/25): Flows/cuts as linear programs, LP duality.
- Week 12 (Nov 13/15): Streaming algorithms, randomized rounding of LPs.
- Week 13 (Nov 20): Other models: online algorithms, distributed algorithms.
- Week 14 (Nov 27/29): Intractability and NP-completeness.
- Week 15 (Dec 4/6): Review of the course, Prep for the final (Slides from the review lecture).
Homeworks and announcements
Homeworks will be posted here, and need to be submitted on the canvas site for the course.
Course project
Please follow the instructions posted on canvas (see the announcements tab). The list of topics is here. Your initial proposal will be due in the last week of October.