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.

CPS130 or equivalent as a hard prerequisite.  If you have never studied algorithms before, please read up on greedy algorithms and dynamic programming, or take CPS130 instead of this course.

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   (Phy 0047)       
Office Hours:    (Kamesh) Wed  13:00-15:00   (D205 LSRC)
                          (Sharath)  Fri     13:00-15:00   (D208 LSRC)

Grading:
Homeworks (30%),  MidTerm (30%), Final (40%). 
This is one of the required courses for the Algorithms area qualifier.
To pass the algorithm qualifier requirement, you need to score 60% on the final OR 75% on the midterm. You also need at least 40% on BOTH the exams.

---

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.
[DPV]   Algorithms by S. Dasgupta, C. Papadimitriou, and U. Vazirani.   

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