Design and Analysis of Algorithms II

(3 Credits)

This course covers techniques in advanced design and analysis. Topics: Amortized analysis of algorithms. Advanced data structures: binomial heaps, Fibonacci heaps, data structures for disjoint sets, analysis of union by rank with path compression. Graph algorithms: elementary graph algorithms, maximum flow, matching algorithms. Randomized algorithms. Theory of NPcompleteness and approach to finding (approximate) solutions to NPcomplete problems. Selected additional topics that may vary. | Knowledge of algorithms and data structures equivalent to CS-GY 6033 . Prerequisite: Graduate standing.