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/ Links to an external site.

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

If you are not sure about pre-requisites, please try and submit Download Homework 0

. [ Download 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 Links to an external site.

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:

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 Links to an external site.] [ Download Slides

] [ Download Notes]
Lecture 2: Data structures for sets of integers, strings. [ Download Slides] [Video Links to an external site.] [ Download Notes]

 

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

Lecture 3: Divide and conquer algorithms. Inductive analysis via recurrences. [Video Links to an external site.][ Download Slides

] [Notes -- Book chapter Links to an external site.]
Lecture 4: Divide and conquer, more examples. [Video Links to an external site.][ Download Slides][Notes -- Book chapter Links to an external site.]

 

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

Lecture 5: Conclude divide and conquer -- linear time selection.  [Video Links to an external site.][ Download Slides

][ Download Notes]
Lecture 6: Dynamic programming: subset sum, sub-problems. [Video Links to an external site.][ Download Slides] [ Download Old survey by Bellman] [Interview with Bellman about the origins Links to an external site.] Download [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 Links to an external site.] Download [Slides]

[ Download Notes]
Lecture 8: Greedy algorithms (scheduling, set cover). [Video Links to an external site.] [ Download Slides][ Download Notes]

 

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

Lecture 9: Minimum spanning tree [Video Links to an external site.][ Download Slides

][ Download Notes]
Lecture 10: Complete analysis of MST, Local search [Video Links to an external site.][ Download Slides][ Download Notes]

 

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

Lecture 11: Shortest paths in graphs [Video Links to an external site.][ Download Slides

][Notes -- book chapter Links to an external site.]
Lecture 12: Shortest paths (contd.) [Video Links to an external site.][ Download Slides][Notes -- book chapter Links to an external site.; 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 Links to an external site.][ Download Slides

] 
Lecture --: Mid-term exam

 

Week 8 (October 15, 17). Randomized algorithms

Lecture 14: Randomness in algorithm design, some examples [Video Links to an external site.][ Download Slides

][ Download Notes]
Lecture 15: Expected running time, quick sort [Video Links to an external site.] [ Download Slides][ Download Notes]

 

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

Lecture 16: Balls and bins, hashing [Video Links to an external site.][ Download Slides

][ Download Notes]
Lecture 17: More on balls and bins, union bound [Video Links to an external site.][ Download Slides][ Download Notes]

 

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

Lecture 18: Sampling and estimation [Video Links to an external site.][ Download Slides

] [ Download Pre-class cheat-sheet] [ Download Notes]
Lecture 19: Streaming algorithms, thoughts about randomized algorithms [Video Links to an external site.][ Download Slides]

 

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

Lecture 20: Formulating "discrete" problems as optimization [Video Links to an external site.][ Download Slides

][Notes on optimization Links to an external site.]
Lecture 21: Linear programming, rounding [Video Links to an external site.][ Download Slides][Notes on optimization Links to an external site.]

 

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

Lecture 22: Algorithmic fairness [Video--Guest Lecture by Prof. Venkatasubramanium Links to an external site.]
Lecture 23: Linear programming relaxations, "rounding"  [Video Links to an external site.][ Download Slides

][Notes on optimization Links to an external site.]

 

Week 13 (November 19, 21). NP completeness

Lecture 24: Intractability, complexity classes, reductions [Video Links to an external site.][ Download Slides

][Notes by Aaron Sidford Links to an external site.]
Lecture 25: Complexity classes. [Video Links to an external site.][ Download Slides][Notes by Aaron Sidford Links to an external site.]

 

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

Lecture 26: Reductions, definitions of NP-hard and NP-complete [Video Links to an external site.][ Download Slides

][Notes by Aaron Sidford Links to an external site.]

 

Week 15 (December 3, 5). Course review

Lecture 27: Reductions, Course review [Video Links to an external site.][ Download Slides -- not annotated

]
Lecture 28: Course review [Video Links to an external site.][ Download Slides -- not annotated]

Course Summary:

Date Details Due
Sat Aug 24, 2019 Assignment Homework 0 due by 11pm
Fri Sep 6, 2019 Assignment Homework 1 due by 11:59pm
Fri Sep 20, 2019 Assignment Homework 2 due by 11:59pm
Wed Oct 16, 2019 Assignment Homework 3 due by 11:59pm
Fri Nov 1, 2019 Assignment Homework 4 due by 11:59pm
Wed Nov 20, 2019 Assignment Homework 5 due by 11:59pm
Fri Dec 6, 2019 Assignment Homework 6 due by 11:59pm
Assignment Final exam  
Assignment Letter Grade  
Assignment Midterm Exam  
Assignment Scaled Total