CS 6150-001 Fall 2019 Advanced Algorithms

Jump to Today

Course description

This course will cover the fundamentals of algorithm design, which is one of the central aspects of computing. We will discuss some basic paradigms, together with techniques for reasoning about algorithms and their asymptotic complexity (in terms of time, memory, etc.). 

Broadly, we will cover the following topics:

  1. Basic paradigms, including divide and conquer, greedy selection, dynamic programming and local search
  2. Randomization in algorithm design
  3. Formulating problems as optimization
  4. Limits of efficient computation, NP completeness, hardness of approximation

Along the way, we will encounter the notion of approximation algorithms for optimization problems, as well as algorithms for other models of computation such as streaming, online and distributed computing.

Background and pre-requisites

The course requires as pre-requisites (a) an undergraduate level discrete structures class, as well as (b) UG-level data-structures or algorithms course. Specifically, the instructor will assume knowledge of notions from graph theory, probability and calculus. Here are some links where you can brush up on the basics:

- Chapters 1-5 of https://algs4.cs.princeton.edu/home/

- Chapters 1, 2, 6, 12 of http://www.cs.utah.edu/~bhaskara/courses/LehmanLeighton.pdf

If you are not sure about pre-requisites, please try and submit Homework 0. [LaTex Source]

Piazza link

This term we will be using Piazza for class discussion. 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 at: 

Logistics

Course email: bhaskara.course@gmail.com

Instructor (Prof Aditya Bhaskara) office hours: Tue, Thu (1:30-2:30 PM). These will be held in MEB 3470.

TA office hours will be

  • Vivek Gupta (keviv9@gmail.com- Wednesday 2:00 pm to 4:00 pm in MEB 3423)
  • Pegah Nokhiz (pegah.nokhiz@utah.edu - Mondays 10:30 am to 12:30 pm in MEB 3421)
  • Kanchana Ruwanpathirana (kanchana.ruwanpathirana@gmail.com - Friday 9:00 am to 11:00 am in MEB 3423)

Grading

The course has six homeworks, the best five of which will count towards your grade. Together, HWs will account for 60% of your grade. We will also have an in-class mid-term (1 hr 15 min) and an in-class final exam (2 hrs). These will count for 15% and 25% of your grade respectively.

The midterm will be on Thursday, October 03 (10:45 - 12:05)

The date for the final exam is determined by the university. This year, it will be on Wednesday, December 11 (10:30 - 12:30). 

Course Policies

A detailed overview of the course policies can be found on: CS 6150 - Course Policies

FAQ

What is the texbook for the course?

As is fairly common with graduate-level courses, we will not follow a single textbook. The lecture slides, videos and notes/links posted will be the main resources. However, given the fairly fundamental nature of the topics covered, there are many excellent resources! Here is a small subset:

  • Book by J. Kleinberg, E. Tardos. Algorithm Design.
  • Classic, comprehensive textbook by T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms.
  • Book by S. Dasgupta, C. Papadimitriou, U. Vazirani. Algorithms.
  • Lecture notes by Jeff Erickson (an excellent set of notes, and many cool exercises).
  • Book by R. Motwani, P. Raghavan. Randomized Algorithms.
  • Book by C. Moore, S. Mertens. Nature of Computation (another fascinating read, for the slightly advanced students).

Why are there no programming assignments?

The aim of the course is to introduce the ideas behind designing and analyzing algorithms. We will thus use only pseudocode to describe algorithms. That said, students should be able to implement any algorithm we see in class.

I will not be able to attend class. Will videos and/or notes suffice?

Starting this year, unfortunately you cannot take the course if you are not able to attend in person. This is because in the past, despite the best efforts of the TAs, we have had a few lectures in which recording has failed, resulting in a bad experience for students. 

Course syllabus

Week 1 (August 20, 22). Topics: Introduction, course overview, basic review.

Lecture 1: Introduction to the course, logistics, analysis basics, data structures (overview, examples). [Video] [Slides] [Notes]
Lecture 2: Data structures for sets of integers, strings. [Slides] [Video] [Notes]

 

Week 2 (August 27, 29). Topics: Divide and conquer, analyzing recurrences.

Lecture 3: Divide and conquer algorithms. Inductive analysis via recurrences. [Video][Slides] [Notes -- Book chapter]
Lecture 4: Divide and conquer, more examples. [Video][Slides][Notes -- Book chapter]

 

Week 3 (September 3, 5). Topics: Divide and conquer (contd.), dynamic programming.

Lecture 5: Conclude divide and conquer -- linear time selection.  [Video][Slides][Notes]
Lecture 6: Dynamic programming: subset sum, sub-problems. [Video][Slides] [Old survey by Bellman] [Interview with Bellman about the origins][Notes]

 

Week 4 (September 10, 12). Topics: Dynamic programming (contd.), Greedy algorithms. 

Lecture 7: Dynamic programming: sub-problems and general principles, traveling salesman problem. [Video][Slides][Notes]
Lecture 8: Greedy algorithms (scheduling, set cover). [Video] [Slides][Notes]

 

Week 5 (September 17, 19). Topics: Greedy paradigm (contd.), local search 

Lecture 9: Minimum spanning tree [Video][Slides][Notes]
Lecture 10: Complete analysis of MST, Local search [Video][Slides][Notes]

 

Week 6 (September 24, 26). Topics: Graph algorithms (continued)

Lecture 11: Shortest paths in graphs [Video][Slides][Notes -- book chapter]
Lecture 12: Shortest paths (contd.) [Video][Slides][Notes -- book chapter; pay attention to sections 4.4.1 and 4.4.2; we saw the latter in class]

 

Week 7 (October 1, 3). Topics: Flows and cuts

Lecture 13: Flows and cuts -- overview [Video][Slides] 
Lecture --: Mid-term exam

 

Week 8 (October 15, 17). Randomized algorithms

Lecture 14: Randomness in algorithm design, some examples [Video][Slides][Notes]
Lecture 15: Expected running time, quick sort [Video] [Slides][Notes]

 

Week 9 (October 22, 24). Randomized algorithms (continued)

Lecture 16: Balls and bins, hashing [Video][Slides][Notes]
Lecture 17: More on balls and bins, union bound [Video][Slides][Notes]

 

Week 10 (October 29, 31). Randomized algorithms (continued)

Lecture 18: Sampling and estimation [Video][Slides] [Pre-class cheat-sheet] [Notes]
Lecture 19: Streaming algorithms, thoughts about randomized algorithms [Video][Slides]

 

Week 11 (November 5, 7). Optimization and linear programming

Lecture 20: Formulating "discrete" problems as optimization [Video][Slides][Notes on optimization]
Lecture 21: Linear programming, rounding [Video][Slides][Notes on optimization]

 

Week 12 (November 12, 14). Misc topics: algorithmic fairness, online algorithms

Lecture 22: Algorithmic fairness [Video--Guest Lecture by Prof. Venkatasubramanium]
Lecture 23: Linear programming relaxations, "rounding"  [Video][Slides][Notes on optimization]

 

Week 13 (November 19, 21). NP completeness

Lecture 24: Intractability, complexity classes, reductions [Video][Slides][Notes by Aaron Sidford]
Lecture 25: Complexity classes. [Video][Slides][Notes by Aaron Sidford]

 

Week 14 (November 26). Intractability (contd.)

Lecture 26: Reductions, definitions of NP-hard and NP-complete [Video][Slides][Notes by Aaron Sidford]

 

Week 15 (December 3, 5). Course review

Lecture 27: Reductions, Course review [Video][Slides -- not annotated]
Lecture 28: Course review [Video][Slides -- not annotated]

Course Summary:

Date Details Due