Advanced Algorithms

3 Credits

Average-case runtime analysis of algorithms. Randomized algorithms and probabilistic analysis of their performance. Analysis of data structures including hash tables, augmented data structures with order statistics. Amortized analysis. Elementary computational geometry. Limits on algorithm space efficiency using PSPACE-completeness theory. Students are expected to already have an undergraduate level of understanding of algorithms, comparable to what is taught in CSE 340 .