• Course Number: 16:198:514
  • Course Type: Graduate
  • Semester 1: Spring
  • Credits: 3
  • Description:

    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.

  • M.S. Course Category: Algorithms & Complexity
  • Category: A (M.S.), A (Ph.D.)
  • Prerequisite Information:


  • Course Links: 16:198:513 - Design and Analysis of Data Structures and Algorithms
  • 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.