Design and Analysis of Algorithms

This course covers techniques for the design and analysis of efficient algorithms. Topics include: divide and conquer, dynamic programing, and greedy design strategies; sorting algorithms including merge sort, randomized quicksort, counting sort, and radix sort; median and order statistics algorithms; sorting lower bound; matrix multiplication and elementary arithmetic algorithms; balanced search trees; augmenting data structures; hash tables; data structures for disjoint sets; amortized analysis; graph traversal algorithms and applications, minimum spanning tree algorithms, shortest path algorithms; maximum flow; introduction to NP completeness.