Basic Information

Course Contents: Review of Basic Concepts, Asymptotic Analysis of Recurrences. Randomized Algorithms. Randomized Quicksort. Algorithm Analysis Techniques - Amortized Analysis. Application to Splay Trees. Priority Queues and Their Extensions: Binomial heaps, Fibonacci heaps, applications to Shortest Path Algorithms. Partition ADT: Weighted union, path compression, Applications to MST. Algorithm Analysis and Design Techniques. Dynamic Programming-Bellman-Ford, Greedy Algorithms. Network Flows-Max flow, min-cut theorem, Ford-Fulkerson, Edmonds-Karp algorithm, Bipartite Matching. NP-Completeness and Reductions.
Text Books:
[CLRS] Introduction to Algorithms, by T. H. Cormen, C. E. Lieserson, R. L. Rivest, and C. Stein, Third Edition, MIT Press.
Reference Books:
[DPV] Algorithms, by S. Dasgupta, C. Papadimitrou, U Vazirani, Mc Graw Hill.
[KT] Algorithm Design, by J. Klienberg and E. Tardos, Pearson Education Limited. Contact Hours for Instructor and TAs:
Meghana: Thursday 2.00pm -- 3.00pm
Pradeep: Friday 2.00pm -- 3.30pm
Dhannya: Monday 2.00pm -- 3.00pm