Computer Science and Engineering

CSE201 Analysis of Algorithms

Rigorous analysis of the time and space requirements of important algorithms, including worst case, average case, and amortized analysis. Techniques include order-notation, recurrence relations, information-theoretic lower bounds, adversary arguments. Analysis of the key data structures: trees, hash tables, balanced tree schemes, priority queues, Fibonacci and binomial heaps. Algorithmic paradigms such as divide and conquer, dynamic programming, union-find with path compression, augmenting paths. Selected advanced algorithms. Introduction to NP-completeness. (Formerly Computer Science 201.)

Requirements

Enrollment is restricted to graduate students; undergraduate students may enroll in this course if they have completed CSE 102 or CSE 106 and have the consent of the instructor.

Credits

5

Quarter offered

Fall, Winter

Instructor

S. Finkelstein, P. Tantalo, A. Van Gelder, D. Helmbold, D. Achlioptas