Computer Science and Engineering

CSE 201 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

Sheldon Finkelstein, Patrick Tantalo, Allen Van Gelder, David Helmbold