Course Descriptions

Prerequisites: 16:198:513. Advanced data structures such as splay trees, link-cut dynamic trees, and finger search trees. Models of parallel computation; selected parallel algorithms. Approximation algorithms and their performance guarantees. Probabilistic algorithms and their analysis. Primality testing. The algorithm for unification. Algorithms for computing the convex hull of a set of points in the plane. Best-first search and variations (hot-node, branch-and-bound), min-max and alpha-beta, and search on game trees. Cocke-Kasami-Younger and Earley's parsing algorithms.