Core material for Computer Science degree candidates. Discussion of representative algorithms and data structures encountered in applications.
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.
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.
6-7 homework assignments. There is a midterm and final examination.