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
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.
[KT05] Algorithm Design, J. Kleinberg and E. Tardos, 2005.
[DPV06] Algorithms, S. Dasgupta, C. Papadimitriou, U. Vazirani, 2006.
[K91] The Design and Analysis of Algorithms, D. Kozen, 1991.
[AHU74] The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft, J. Ulman, 1974.
[MU05] Probability and Computing: Randomized Algorithms and Probabilistic Analysis, M. Mitzenmacher, E. Upfal, 2005.
[MR95] Randomized Algorithms, R. Motwani, P. Raghavan, 1995.
[V04] Approximation Algorithms, V. Vazirani, 2004.
For background reading on probability, algorithms, and complexity theory, I recommend:
[CLRS09] Introduction to Algorithms (3rd edition), T. Cormen, C. Leiserson, R. Rivest, and C. Stein, 2009.
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.
Randomized algorithms: basic techniques from discrete probability, and applications to min-cut algrorithm, randomized quicksort, randomized median, polynomial-identity testing.
Greedy algorithms: spanning trees, Steiner trees, matroids, arborescences, and multicast cost-sharing.
Network flows: maximum flows and minimum cuts, the preflow-push algorithm, minimum-cost flows, multicommodity flows, and applications to matching, scheduling, network routing and vision.
Dynamic programming: basic dynamic programming technique, dynamic programming on trees, tree decomposition, and algorithms for graphs with bounded tree width.
NP-completeness: Intractability
Approximation algorithms: greedy algorithms, local search, on-line algorithms, primal-dual algorithms, linear programming.
Cryptography and number theory: Integer arithmetic, Csanky's algorithm, Chistov's algorithm, matrix rank, linear equations and polynomial gcds, FFT, Luby's algorithm, primality testing
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)
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.
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.
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%
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.