CS 6150-001 Fall 2020 Graduate Algorithms

Jump to Today

Quick links:  Course Videos Page

                      Recitation Zoom Link: https://utah.zoom.us/j/96735883277 (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/

- 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 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, 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

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 [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/

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:

  • 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).

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). [Slides] [Notes] [Annotated Slides]
Lecture 2: Data structures [Slides] [Notes] [Annotated Slides]

 

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

Lecture 3:  DATA STRUCTURES, DIVIDE & CONQUER [Slides] [Notes -- Book chapter] [Annotated Slides]
Lecture 4: Divide and conquer, more examples. [Slides] [Notes -- Book chapter] [Annotated Slides]

 

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

Lecture 5: Conclude divide and conquer [Slides -- not annotated]  [Notes] [Annotated Slides]
Lecture 6: Dynamic programming [Slides -- not annotated] [Old survey by Bellman] [Interview with Bellman about the origins][ Notes ][Annotated Slides]

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

Lecture 7: Dynamic programming [Slides -- not annotated][ Notes ] [Annotated Slides]
Lecture 8: (Make-up) Linear time selection. [Annotated Slides] [Youtube link]

 

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

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

 

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

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

 

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

Lecture 13: Greedy Algorithms, Local search algorithms [Slides -- not annotated] [Annotated Slides] [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 [Slides -- not annotated] [Annotated Slides]
Lecture 15: Shortest paths overview, Randomized Algorithms [Slides -- not annotated] [Annotated Slides] [ Notes ]

Shortest paths [Slides][Notes -- book chapter; pay attention to sections 4.4.1 and 4.4.2]

 

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

Lecture 16: Randomized Algorithms [Slides -- not annotated] [ Notes ] [Annotated Slides]

Lecture 17: Expected running time (contd.) [Slides -- not annotated] [Annotated Slides] [Notes_Lec16_f20.pdf]

 

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

Lecture 18: Hashing [Slides -- not annotated] [Annotated Slides]

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

 

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

Lecture 20: Sampling and estimation [Slides -- not annotated] [Annotated Slides] [Notes20_f20.pdf]

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

 

Week 12: Optimization 

Lecture 22: optimization formulation  [Slides -- not annotated][Annotated Slides]  [Notes on optimization]
Lecture 23: Optimization formulations, Linear programming [Slides -- not annotated] [Annotated Slides]

[Notes on optimization]

Week 13 (November 17, 19). Linear Programming 

Lecture 24:Linear programming [Slides -- not annotated] [Annotated Slides]

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

 

Week 14 (November 24).  Limits of efficient algorithms

 

Lecture 26: Intractability, complexity classes, reductions [Slides][Notes by Aaron Sidford] (Reductions, definitions of NP-hard and NP-complete )

Week 15 (December 1, 3). Course review

Lecture 27: Course review [Slides -- not annotated][Annotated Slides]
Lecture 28:  Course Review [Annotated Slides]

Course Summary:

Date Details Due