This course will cover algorithm design techniques at a graduate level. Topics include graph algorithms, shortest paths, amortization and search trees, randomization, hashing, fingerprinting, divide and conquer applied to FFT and matrix multiplication, network flows, matchings, stable marriage, linear programming, simplex algorithm, zero-sum gamnes, duality, and NP-Completeness. You need CPS130 or equivalent as a prerequisite.

Assignments and grades are posted via blackboard
Slides that explain the material from the Kleinberg-Tardos book can be found here

---

Administration: 
Lectures:           Tue/Thu 1:15-2:30   (D106 LSRC)       
Office Hours:    (Kamesh) Wed  13:00-14:30   (D205 LSRC)
                          (Sudheer) Mon 14:00-16:00 (D206 LSRC)

Grading:
Homeworks (30%),  MidTerm (30%), Final (40%). 
This is one of the required courses for the Algorithms area qualifier.
A grade of 60% on the final OR 75% on the midterm to pass the algorithm qualifier requirement.

---

Course Textbooks (optional):
[CLRS]  Introduction to Algorithms by T. Cormen, C. Leiserson, R. Rivest, and C. Stein. 
[KT]      Algorithm Design  by Jon Kleinberg and Eva Tardos.

Additional Reading: 
(Lec 2)     Buckets, heaps, lists, and monotone priority queues
(Lec 2)     Fibonacci Heaps used to implement Dijkstra's and Prim's algorithms in O(m + n log n) time
(Lec 7)     The Burrows-Wheeler Transform (aka bzip on UNIX): Clever Compression using MTF
(Lec 11)    Skip Graphs -- Peer-to-peer routing using skip lists
(Lec 14)    Survey article on network applications of Bloom filters
(Lec 14)    Consistent Hashing -- One of the key ideas behind Akamai Technologies
(Lec 14)    Distributed hash tables -- Efficient data management in P2P networks
(Lec 14)    Code-division Multiple Access (CDMA) uses "hashing" for wireless communication.
(Lec 20)    Packet switching: Great application of fast table lookups, permutation networks & matchings
(Lec 20)    Stable marriages