*****COURSES ARE SUBJECT TO CHANGE*****
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. Enrollment restricted to graduate students; undergraduate students may enroll in this course if they have completed either course 102 or Computer Engineering 177 and have the consent of the instructor. D. Achlioptas, D. Helmbold, M. Schlag, A. Van Gelder
While the information on this web site is usually the most up to date, in the event of a discrepancy please contact your adviser to confirm which information is correct.