Advanced Algorithms

Computer Science 284/484
University of Rochester
Spring 2014



Instructor: Muthu Venkitasubramaniam

Time: TR 12:30-13:45
Place: CSB 632
Course Web page: http://www.cs.rochester.edu/courses/284/spring2014/

Office Hours: TBD

Reading

There is no required text for the course. You may find the following books to be useful references. Note, however, that we will not always be following the same notations as these books.

For background reading on probability, algorithms, and complexity theory, I recommend:


Topics Outline

The course is organized around a few fundamental themes. The exact coverage is subject to change. Topics below will be covered as time permits; we will probably not have time to cover everything.

Lectures

1/16 Multiplicative weights update methods I – Learning from experts. (Reference: Alexander Mądry's Notes.)

1/21 Multiplicative weights update methods II – How to get rich!

Short introduction to probability, random variables, expectation. (Reference: Babai's Notes.)

Topic: Randomized Algorithms

Reading: [CLRS09] chapters 3,4,5; [KT05] chapter 13; [MR95] chapter 1; [MU05] chapters 1,2,3,4;

1/23 Contention Resolution and Global Minimum Cut (Chapter 13 [KT05])

1/27 Rrandomized Median and Randomized Quicksort (Chapter 13 [KT05])

1/29 Randomized Algorithm for MAX 3-SAT and Universal hashing (Chapter 13 [KT05])

2/4 Finding closes pair of points (Chapter 13 [KT05])

2/6 Primality Testing (Guest Lecture by Scott Ames)

2/11-2/13 Primality Testing Continued (Chapters 38-39 [K91])

2/25 First Mid-Term

Greedy Algorithms - Matroids and Minimum Spanning Tree (Chapters 2,3 [K91])

Greedy Algorithms (Chapter 4 [KT05])

Dynamic Programming (Chapter 6 [KT05])

Network Flows (Chapter 7 [KT05])

Data Structures - Union/Find (notes (Courtesy: Avrim Blum))

Data Structures - Binomial Heaps (Chapter 19 [CLRS 2/e - note this chapter is only in the second edition and not the third edition])

P vs NP and NP completeness (PDF1,PDF2)

Prerequisites

CS 280 (or equivalent), MTH150 (or mathematical maturity), or permission of instructor.
The main skills that will be assumed from these courses are: 1) the ability to understand and write formal mathematical definitions and proofs and 2) comfort with reasoning about algorithms, such as proving their correctness and analyzing their running times. It is also important that you are familiar with basic probability.

Course Administration

All homeworks and grades will be posted on blackboard. Course announcement will also be made through blackboard. We will be using Piazza for offline discussions and notes.

Grading

There will be 4-5 homeworks and 2 mid-terms and a final. The grade will be based on homework assignments, exams and class participation.

Homeworks 30%

Mid-Terms (20+20)%

Final 30%

Homework Policy

You are free to collaborate with other students on the homework, but you must turn in your own individually written solution and you must specify the names of your collaborators. Additionally, you may make use of published material, provided that you acknowledge all sources used. Note that it is a violation of this policy to submit a problem solution that you are unable to explain orally to me. Typed problem sets are strongly preferred.