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
Here are the timings for the TA office hours.
- Hong Xu: Monday 2:00 - 4:00 PM
- Sravan Kumar: Tuesday 3:00 - 5:00 PM
- Maheshakya Wijewardena: Wednesday 3:00 - 5:00 PM
- Amin Mohammadi: Thursday 4:00 - 6:00 PM
To send email to the TAs (+ instructor), 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, Chebychev's inequality
- Week 9 (October 23, 25). Randomized algorithms (continued)
Lecture 17: Chernoff bounds, interesting randomized algorithms
- Week 10 (October 30, November 1). Optimization formulations, linear programming.
Lecture 18: Concluding thoughts on randomized algorithms; optimization formulations
Lecture 19: Linear programming, integrality.
Here is a short note on how to write the shortest path problem as an (integer) optimzation.
- Week 11 (November 6, November 8). Linear programming.
Lecture 20: Geometry of linear programming -- simplex algorithm and correctness
Lecture 21: LP for combinatorial problems, rounding
- Week 12 (November 13, November 15). Rounding, duality
Lecture 22: Randomized rounding and approximation algorithms
Lecture 23: Duality. Notes by Luca Trevisan.
- Week 13 (November 20). Intractability and NP completeness
Lecture 24: Lower bounds on computation, NP, Cook-Levin theorem
- Week 14 (November 27). Intractability and NP completeness
Lecture 25: Intractability, NP completeness, Reductions
- Week 15 (December 5, 6). Intractability (conclusion), Course review
Lecture 26: Examples of reduction, hardness of approximation, course review
Lecture 27: Review.
Homeworks and announcements
Homeworks will be posted here, and need to be submitted on the canvas site for the course.
- (Optional) Homework 0. This homework is meant to give a rough sense of the background needed for the course. [solutions]
- Homework 1. Due on Monday, September 10, 11:59 PM. [solutions]
- Homework 2. Due on Friday, September 28, 11:59 PM. [solutions] (TA draft)
- Homework 3. Due on Friday, October 19, 11:59 PM. [solutions]
- Homework 4. Due on Monday, November 5, 11:59 PM. [solutions]
- Homework 5. Due on Monday, November 26, 11:59 PM. [solutions]
- Homework 6. Due on Friday, December 7, 11:59 PM.
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.