Course Details
16:198:514 - Design And Analysis Of Data Structures And Algorithms II
- 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:
16:198:513
- 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.
