CS 6150-001 Fall 2015 Advanced Algorithms
This class is about advanced algorithms. Unlike previous incarnations of this class that you may have looked at before, I will not be covering core topics that are usually covered in an undergraduate class in algorithms, such as basics of dynamic programming, divide and conquer, greedy algorithms and the basics of NP-completeness.
Rather, I'll be taking things to the next level, covering topics that are of arguably far more importance for algorithm design in today's world, especially a data-centric one.
Course Times.
Lecture: T TH WEB L105: 1045-1205
Instructor Office Hours: Th 1-3, MEB 3404. Email: suresh@cs.utah.edu
TA Office Hours: Pingfan Tang, M 9am-11am, MEB 4158
Teaching Assistants
- Ankit Agarwal
- Chitradeep Dutta Roy
- Pingfan Tang
Course Mechanics.
As in past years, there will be no exams for this class. The total grade will break down as
- 75% homework assignments (5-6)
- 25% project (more details below)
Homeworks.
Please read the homework guidelines.
Project.
The project is to read a paper
Students will form groups of at most 2 people for their project. For more details please see the project guidelines.
Reading Material.
There is no fixed textbook for this class. I'll provide readings as we go along. For source material, I will use
- Jeff Erickson's notes on algorithms
- Sanjeev Arora's notes on advanced algorithms
- Chapters from Algorithm Design by Kleinberg and Tardos (slides by Kevin Wayne)
Topics and lecture outline. (lecture number in parenthesis)
Core material.
- Randomized Algorithms
- (1,2) Hashing
- (lecture 1) and my class notes,
- (lecture 2) and my class notes
- (3) Min cuts (lecture 3)
- (4) Fingerprinting (Freivald's technique (Section 2), equality testing (Section 2.1) and document similarity (Section 2)) (lecture 4) (The audio is not working for this lecture)
- (5) tail bounds (lecture 5) (my class notes)
- Approximation Algorithms (general notes)
- (6) Definitions and simple examples (median, frequent elements) (lecture 6)
- (7) Approximations for hard problems: vertex cover, set cover, TSP. (lecture7), my class notes
- (8) More about TSP. (lecture 8) and my notes.
- (9,10) TSP and PTASs (Knapsack) (my notes) (lecture 9 , lecture 10)
- (11) Interlude: How to read a project paper. We will pick this paper from FOCS 2007 and attempt to read it in real time. ( lecture 11)
- Basic optimization: Linear programming, polyhedral optimization, flows and matchings
- (12, 13) Flows and cuts (lecture 12 , lecture 13)
- (14, 15) Min cuts and max flows: applications and extensions (lecture 14 , lecture 15)
- (16) Linear programming and duality. (lecture 16)
- (17, 18) LP-duality continued, and LP-rounding (lecture18)
- Multiplicative weight updates (or zombie binary search)
- (19) Lecture notes on MWU (part one, two) and the connection to zombies. (lecture 19). My notes.
Advanced material.
- Advanced optimization
- (20) Semidefinite programming (Chapter 6.1) (lecture 20)
- (21) Free-for-all Lecture. Bring your questions ! Especially about linear programming and semidefinite programming (lecture 21).
- Dealing with large data
- (22) Core sets and sketches (lecture 22)
- (23) Random projections and the JL Lemma
- (24) Streaming algorithms
Miscellaneous Lectures
- (25) Algorithmic Game Theory
- (26) Algorithmic Fairness
- (27) Interactive Proofs
- (28) How to cut a cake, fairly.
Course Summary:
Date | Details | Due |
---|---|---|