CS 6150-001 Fall 2015 Advanced Algorithms

CS 6150-001 Fall 2015 Advanced Algorithms

This class is about advanced algorithms. Unlike previous incarnations of this class that you may have looked at before, I will not be covering core topics that are usually covered in an undergraduate class in algorithms, such as basics of dynamic programming, divide and conquer, greedy algorithms and the basics of NP-completeness. 

Rather, I'll be taking things to the next level, covering topics that are of arguably far more importance for algorithm design in today's world, especially a data-centric one. 

Course Times.

Lecture: T TH WEB L105: 1045-1205

Instructor Office Hours: Th 1-3, MEB 3404. Email: suresh@cs.utah.edu

TA Office Hours: Pingfan Tang, M 9am-11am, MEB 4158

Teaching Assistants

  • Ankit Agarwal
  • Chitradeep Dutta Roy
  • Pingfan Tang

Course Mechanics.

As in past years, there will be no exams for this class. The total grade will break down as 

  • 75% homework assignments (5-6)
  • 25% project (more details below) 


Please read the homework guidelines.


The project is to read a paper 

Students will form groups of at most 2 people for their project. For more details please see the project guidelines

Reading Material.


There is no fixed textbook for this class. I'll provide readings as we go along. For source material, I will use

Topics and lecture outline. (lecture number in parenthesis)

Core material.

Advanced material.

  • Advanced optimization
  • Dealing with large data
    • (22) Core sets and sketches (lecture 22)
    • (23) Random projections and the JL Lemma
    • (24) Streaming algorithms

Miscellaneous Lectures

    • (25) Algorithmic Game Theory
    • (26) Algorithmic Fairness
    • (27) Interactive Proofs
    • (28) How to cut a cake, fairly. 


Course Summary:

Date Details