Skip to content Skip to navigation

Design And Analysis Of Data Structures And Algorithms II

16:198:514

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.

Credits: 
3
Category: 
A
Prerequisite: 
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.

Professor: 
Martin Farach-Colton
William Steiger
Mario Szegedy
Semester: 
Spring
Course Type: 
Graduate

Check the University Schedule of Classes to see if this course is open.

Request a Special Permission Number here if the class is full.