Description
This course goes beyond 198:513 in introducing the student to new concepts and techniques used in the study of algorithms. It is intended to serve students specializing in a number of different areas within computer science.
Martin Farach-Colton, Michael Fredman, William Steiger, Mario Szegedy, Endre Szemeredi
Credits: 3
Category: A
Prerequisites: 16:198:513
Semesters Offered:Spring
Topics: The material actually covered in this course tends to vary with the instructor. Typically, it is some subset of the following set.
* 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.
Throughout the course, recurring fundamental concepts and techniques such as divide-and-conquer, dynamic programming, backtracking, and greedy algorithms will be emphasized as they occur in different settings.
Expected Work: Homework assignments, a midterm, and a final.
