Skip to content Skip to navigation

Design And Analysis Of Data Structures And Algorithms II


This course goes beyond 16: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.

A (M.S.)
A (Ph.D.)

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.

Teaching Professors Names: 
Martin Farach-Colton
William Steiger
Mario Szegedy