Analysis of Algorithms

Welcome to CMPS 201: Analysis of Algorithms

This course stresses the 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.

 

 

Required Textbook: Algorithm Design by Kleinberg and Tardos

Slides: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/

Announcements:

  • No class on 26th November 2014. Drop your homework in the mailbox at Baskin Engineering E2 341-A
  • Subsitute Instructor: Prof. Dmitris Achiloptas will lecture on 8th and 10th of December 2014.
  • No office hours on 10th of December 2014.
  • Mid-term exam on Wednesday 5th of November 2014 during class.
  • Final exam on Wednesday 17th of December 2014, 7:30 - 10:30 pm. 

Instructors and Assistants