Skip to content Skip to navigation

Design and Analysis of Data Structures and Algorithms

16:198:513

Core material for Computer Science degree candidates. Discussion of representative algorithms and data structures encountered in applications.

Credits: 
3
Category: 
A (M.S.)
A (Ph.D.)
Prerequisite: 

Familiarity with Prim and Kruskal minimum spanning tree algorithms and Dijkstra shortest path algorithm.
For MS students 16:198:512 is a pre-requisite.  
Ph.D. students can directly register for 513.

Semesters: 
Fall, and Spring
Topics: 

Worst case, average case, and amortized analysis. Data structures: search trees, hash tables, heaps, Fibonacci heaps, union-find. Algorithms: string matching, sorting and ordering statistics, graph algorithms. NP-completeness.

Expected Work: 

6-7 homework assignments. There is a midterm and final examination.

Teaching Professors Names: 
Martin Farach-Colton
Bahman Kalantari
Shan Muthukrishnan
William Steiger