Analysis of Algorithms

Instructor

• Reza Pulungan

Schedule

• Lectures
  • Thursdays: 13:00-15:30, at SIC 3.01
• Exams
  • Mid-term: Oct, 25 - Nov. 5, 2010
  • Final: Jan. 3 - 15, 2011

Textbooks

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms (2nd ed.), MIT Press, 2001.
• A. V. Aho, J. E. Hopcroft, and J. D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. (Reading)

Grading

• Exercises: 20%
• Mid-term exam: 40%
• Final exam: 40%

Lectures

Lecture 0 (August 26, 2010)

• Lecture Notes

Lecture 1 (September 2, 2010)

• O, Omega, and Theta-notations; Recurrences.

Lecture 2 (September 23, 2010)

• Recurrences.

Lecture 3 (September 30, 2010)

• Quicksort and Limitations of Comparison Sorts.

Lecture 4 (October 7, 2010)

• Divide and Conquer.

Lecture 5 (October 14, 2010)

• Order Statistics.

Lecture 6 (October 21, 2010)

• Hashing I.

Lecture 7 (November 18, 2010)

• Hashing II.

Lecture 8 (November 25, 2010)

• Binary Search Tress + Red-Black Trees.

Lecture 9 (December 9, 2010)

• Red-Black Trees + Skip Lists.

Lecture 10 (December 16, 2010)

• Skip Lists + Amortized Analysis.

Lecture 11 (December 23, 2010)

• Dynamic Programming.

Lecture 12 (December 29, 2010)

• Greedy Algorithms.