CS 5150/6150 -- Advanced Algorithms



Jump to class schedule, or homeworks.

Course Outline

This course will cover the fundamentals of algorithm design, one of the most important aspects of computing. We will discuss some basic paradigms, with an emphasis on mathematically reasoning about the correctness and complexity of algorithms. The course requires a knowledge of UG-level data structures and algorithms, as well as basic graph theory and probability. Most importantly, you need to be comfortable understanding and coming up with mathematical proofs.

A rough set of topics we will cover is the following:

  1. Overview of divide and conquer, greedy algorithms and local search, and dynamic programming
  2. Randomization in algorithm design
  3. Optimization and linear programming formulation of problems
  4. Limits of efficient algorithms: NP completeness, hardness of approximation
  5. Other models: online algorithms, distributed computation

The focus will be on how to design algorithms for new problems, and on how to reason about the "performance" of an algorithm. Performance, based on the context, can refer to the space/time complexity, the approximation guarantee, the run-time in a distributed model, or a combination of these measures. In short, the goal is to give a taste of algorithm design, and the kind of questions we care about.

Prerequisites

As most first year MS/PhD students are expected to take this class, there are no enforced pre-reqs. However, a knowledge of basic data structures, graph theory, calculus, and probability will be assumed. To get a sense of what I mean, take a look at chapters 1-6 here. It is also crucial to be comfortable with reading and designing mathematical proofs. A good place to brush up on your math background is the monograph of Lehman and Leighton (chapters 1, 2, 3, 6, 12, 18, 20, 21, 22). Also, take a look at HW0. This is an optional HW, but the problems are meant to give a sense of the background needed. If any of the problems takes over half an hour for you to solve, consider discussing with the instructor.

Programming?

The course is about designing and reasoning about algorithms. We will not explicitly do any implementation, but you should be able to (at least roughly) implement any algorithm we cover. The course project will involve implementation. Any instructor-approved programming language can be used for the project.

Logistics

Time        :   10:45 am - 12:05 pm, Tuesday and Thursday

Location  :    WEB L105

Instructor and Office Hours

TAs and office hours

For the TA office hours (+locations) please check the canvas page.
To send email to the TAs, please use this address: utah-algo-ta@googlegroups.com

Exams and grading

The homeworks (see below) will count for 60% of the final grade (best five out of six will be considered). The exam and project will each count for 20%. This will be used to obtain a total score. Grading will be based on a combination of this score and the score in the exam.

Exam: we will have one examination for the course. The date/time of this exam are set by the university, available here. It will be on Tuesday, December 11, 2018, 10:30 am - 12:30 pm.

Textbooks and references

There is no single textbook for the course, so the lecture slides/videos and the lecture notes will be important references. Apart from these, the following notes/textbooks are all excellent references for different portions of the class. The first three are standard algorithms textbooks. They cover all the topics we will see in the first half of the course (and a lot more).

Course schedule

Here is the tentative schedule for the course. We will post links to lecture videos, slides and notes as the semester progresses.


Homeworks and announcements

Homeworks will be posted here, and need to be submitted on the canvas site for the course.

Course project

Please follow the instructions posted on canvas (see the announcements tab). The list of topics is here. Your initial proposal will be due in the last week of October.