CS 6150-001 Fall 2021 Graduate Algorithms

Jump to Today

Quick links:  Course schedule, video links

Course description

Algorithms are at the core of any computation. Designing efficient algorithms is thus one of the basic goals in many areas of CS. The goal of the course is to study some of the fundamental principles and techniques. Given the growing role of algorithms in our lives, it is crucial to understand if/when algorithms produce the "correct" output (via rigorous mathematical analysis), and to study the running time and resource utilization of algorithms. 

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 (e.g., linear and convex programming)
  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 briefly study 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 mathematics course, as well as (b) UG-level data-structures 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 as follows:

- In person, for 15 min after each lecture
- On zoom, using the link https://utah.zoom.us/j/95080954715 (Passcode: 61505150) time: 10-11 AM on Wednesdays.

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

  • Frost Mitchell
    • MEB Room 3515, Thursdays 10am-12pm
  • Yo Mizutani
    • Zoom, Mondays, 4-5 pm
    • MEB Room 3515, Thursdays, 4-5 pm
  • Nitish Shingde
    • MEB Room 3159, Thursdays 3-4pm
    • Zoom, Fridays 11:30am-12:30pm (Passcode: 782272)
  • Anuja Garg
    • MEB Room 3225, Mondays 12pm-1pm
    • MEB Room 3159, Wednesdays 12pm-1pm

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.

Grading

There are two main components that contribute to your grade:

Homeworks: There will be six homeworks, the best five of which will count towards your grade. Together, HWs will account for 65% 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 (date announced by registrar).  These exams will be administered on Canvas. The midterm and final will account for 15% and 20% of the course grade.

Late submissions:  The submission system will be open until 4 days after the HW due date. For each late day after the due date, there will be a 10% penalty. This semester, all students get 6 penalty-free "late days" that you can distribute among the homeworks (you won't get penalized if you have enough "late days" in your bank, but your "late days" count will get reduced accordingly). 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 determined using cutoffs as determined in the course logistics document. [Logistics for CS 5150/6150]

More course policies

This semester is a challenging one since we will be trying to return to normal. So it is possible that some of the policies change 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: 

The course will have lectures in person, and you are expected to attend them and participate in class. That said, we will do our best to record all the lectures and make them available online (via the course schedule page). 

FAQ

What is the textbook 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).

 

Course Summary:

Date Details Due