CS 6150-001 Fall 2020 Graduate Algorithms

Jump to Today

Quick links:  Course Videos Page

                      Recitation Zoom Link: https://utah.zoom.us/j/96735883277 Links to an external site. (Pwd: 51506150)

Course description

Algorithms are at the core of any computation. It is thus crucial to understand (a) if an algorithm always produces the correct output, (b) how long it takes to produce the output as a function of the input size (or some other parameters), (c) how much memory and other resources are necessary for the computation. The aim of this course is to study some fundamental principles of algorithm design. We will discuss some basic paradigms, together with techniques for reasoning about algorithms and their complexity and performance. 

Broadly, we will cover the following topics:

  1. Basic paradigms, including divide and conquer, greedy selection, dynamic programming and local search
  2. Using 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. We will also see the role that the computational "model" plays in designing algorithms. To illustrate, we will see 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 Quiz 0 (which will be posted soon).

Logistics

Course email: bhaskara.course@gmail.com

Emails related to your standing in the course and other "protected" information should be sent to bhaskara@cs.utah.edu; you should also use your @utah.edu address for this.

Instructor (Prof Aditya Bhaskara) office hours this semester will be 3-4 PM on Mondays and 11 AM-12 PM on Wednesday. (https://utah.zoom.us/j/96735883277 Links to an external site., Passcode: 51506150)

TAs: We have three TAs for the course, and here are their names and the details of their office hours.

Class discussions:

We will be using Piazza for class discussion. Rather than emailing questions to the teaching staff, please post your questions on Piazza. You can also send private messages to the instructors in case you have questions about your grades, your performance, etc.

Here is the link for signing up: piazza.com/utah/fall2020/cs51506150 Links to an external site.

Online course logistics: To keep them all in one place, the Zoom links and recordings will be posted on the "Course Video Links" page.

Fall 2020 CS 5150/6150 Zoom Guidelines are in [ Download Zoom Guidelines].

Grading

The course grading is simplified this semester.  We have two components:

Homeworks: There will be six homeworks, the best five of which will count towards your grade. Together, HWs will account for 60% of your grade.

Exams: We will have two exams, one in the middle of the term (first week of October), and the other at the end of the semester (first week of December).  These exams will be administered on Canvas. They will each account for 20% of the course grade.

Late submissions:  This semester, all students get 10 "late days" that you can distribute among the homeworks. Beyond this, there will be a 10% penalty per day (we will be mindful and apply the late penalty for HWs where you scored lower). 

Medical exceptions:  If you have a medical reason for requiring an exception to the above (as well as potentially re-scheduling the exams), please make sure you have medical records and contact the instructor ASAP (bhaskara@cs.utah.edu, or send a private message on Piazza/Canvas).

Final grade: The final grade is not based on absolute thresholds, as it tends to vary from year to year (and may vary more this year). We will ensure that about 25% of the students receive A/A-, about 50-60% receive B-/B/B+, and the remainder will receive lower grades. 

CR/NC option:  Students may think that CR/NC is equivalent to "pass/fail". This is only in spirit, and is not exactly true. To be clear, you will receive a CR grade if your grade is C- or higher. Else, you will receive NC (even if you had an officially "pass" grade such as a D). 

More course policies

This semester is a challenging one for all of us. So I expect the policies to change slightly as we go along. So please **check this space periodically**.

The College of Engineering has compiled a list of semester guidelines that will also apply to this course: https://www.coe.utah.edu/students/current/semester-guidelines/ Links to an external site.

The course is in "IVC" mode, so we will have Zoom sessions as well as pre-recorded videos, see the Logistics tab above. Grading policies were already covered above.

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:

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. (If not, please talk to the TAs.)

Course syllabus

Week 1 (August 25, 27). Topics: Introduction, course overview, basic review.

Lecture 1: Introduction to the course, logistics, analysis basics, data structures (overview, examples). [ Download Slides

] [ Download Notes] [ Download Annotated Slides]
Lecture 2: Data structures [ Download Slides] [ Download Notes] [ Download Annotated Slides]

 

Week 2 (September 1, 3). Topics: Divide and conquer, analyzing recurrences.

Lecture 3:  DATA STRUCTURES, DIVIDE & CONQUER [ Download Slides

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

 

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

Lecture 5: Conclude divide and conquer [ Download Slides -- not annotated

]  [ Download Notes] [ Download Annotated Slides]
Lecture 6: Dynamic programming [ Download Slides -- not annotated] [ Download Old survey by Bellman] [Interview with Bellman about the origins Links to an external site.] Download [ Notes ][ Download Annotated Slides]

Week 4 (September 15, 17). Topics: Dynamic programming (contd.). 

Lecture 7: Dynamic programming [ Download Slides -- not annotated

][ Download Notes ] [ Download Annotated Slides]
Lecture 8: (Make-up) Linear time selection. [ Download Annotated Slides] [Youtube link Links to an external site.]

 

Week 5 (September 22, 24). Topics: Dynamic programming (contd.), greedy algorithms 

Lecture 9: Dynamic programming[ Download Slides -- not annotated

][ Download Notes] [ Download Annotated Slides]
Lecture 10: Dynamic programming (finale), Greedy algorithms [ Download Slides -- not annotated] [ Download Notes] [ Download Annotated Slides]

 

Week 6 (September 29, October 1). Topics: Greedy algorithms (continued)

Lecture 11: Greedy Algorithms [ Download Slides -- not annotated

] [ Download Annotated Slides]
Lecture 12: Greedy Algorithms [ Download Slides -- not annotated] [ Download Annotated Slides] [ Download lec12_2020.pdf]

 

Week 7 (October 6, 8). Topics: Greedy Algorithms, and local search

Lecture 13: Greedy Algorithms, Local search algorithms [ Download Slides -- not annotated

] [ Download Annotated Slides] [ Download Notes13_f20.pdf]
Lecture --: Mid-term exam

 

Week 8 (October 13, 15). Shortest paths, Intro to randomized algorithms

Lecture 14: Local search (conclude), Shortest path [ Download Slides -- not annotated

] [ Download Annotated Slides]
Lecture 15: Shortest paths overview, Randomized Algorithms [ Download Slides -- not annotated] [ Download Annotated Slides] [ Download Notes ]

Shortest paths [ Download Slides

][Notes -- book chapter Links to an external site.; pay attention to sections 4.4.1 and 4.4.2]

 

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

Lecture 16: Randomized Algorithms [ Download Slides -- not annotated

] [ Download Notes ] [ Download Annotated Slides]

Lecture 17: Expected running time (contd.) [ Download Slides -- not annotated

] [ Download Annotated Slides] [ Download Notes_Lec16_f20.pdf]

 

Week 10 (October 27, 29). Hashing, Sampling, Randomized algorithms (continued)

Lecture 18: Hashing [ Download Slides -- not annotated

] [ Download Annotated Slides]

 [ Download Pre-class cheat-sheet

][ Download Notes18_f20.pdf]
Lecture 19: Hashing (contd.), introduction to sampling [ Download Slides -- not annotated] [ Download Annotated Slides][ Download Notes_Lec19_f20.pdf]

 

Week 11 (November 3, 5). Sampling, concluding randomized algorithms

Lecture 20: Sampling and estimation [ Download Slides -- not annotated

] [ Download Annotated Slides] [ Download Notes20_f20.pdf]

Lecture 21: randomized algorithms wrap up [ Download Slides -- not annotated

][ Download Annotated Slides]

 

Week 12: Optimization 

Lecture 22: optimization formulation  [ Download Slides -- not annotated

][ Download Annotated Slides]  [Notes on optimization Links to an external site.]
Lecture 23: Optimization formulations, Linear programming [ Download Slides -- not annotated] [ Download Annotated Slides]

[Notes on optimization Links to an external site.]

Week 13 (November 17, 19). Linear Programming 

Lecture 24:Linear programming [ Download Slides -- not annotated

] [ Download Annotated Slides]

Lecture 25:  LP for combinatorial problems [ Download Slides -- not annotated

] [ Download Annotated Slides]

 

Week 14 (November 24).  Limits of efficient algorithms

 

Lecture 26: Intractability, complexity classes, reductions [ Download Slides

][Notes by Aaron Sidford Links to an external site.] (Reductions, definitions of NP-hard and NP-complete )

Week 15 (December 1, 3). Course review

Lecture 27: Course review [ Download Slides -- not annotated

][ Download Annotated Slides]
Lecture 28:  Course Review [ Download Annotated Slides]

Course Summary:

Date Details Due
Fri Sep 18, 2020 Assignment Homework 1 due by 11:59pm
Fri Oct 2, 2020 Assignment Homework 2 due by 11:59pm
Sat Oct 10, 2020 Quiz Midterm due by 11:59pm
Sun Oct 11, 2020 Quiz Midterm
(1 student)
 due by 11:59pm
Sun Oct 25, 2020 Assignment Homework 3 due by 11:59pm
Tue Nov 10, 2020 Assignment Homework 4 due by 11:59pm
Wed Nov 25, 2020 Assignment Homework 5 due by 11:59pm
Assignment Extra Credit HW4  
Quiz Final Exam
(1 student)
  
Quiz Final Exam  
Assignment Letter Grades  
Assignment Scaled Total