CS 4/5703 Analysis of Algorithms
Fall 2008

• ANNOUNCEMENT: Final exam: Friday December 12, 8:00-10:00am, in classroom.
  
  Some lecture slides for your reference:
• Class note 1;
• Class note 2; HW#1;
• Class note 3;
• Class note 4;
• Class note 5 on heapsort;
• Class note 6 on quicksort;
• Class note 7 on BST;

Analysis of Algorithms

This is the first course on algorithm design and analysis. In data structures we have looked at "baby" algorithms, big-O, sorting, etc., now we shold be prepared for the standard algorithm course.

• Course syllabus

Goal

At the end of the semester you should:

• be familiar with fundamental algorithms and algorithmic techniques,
• given a particular application, be able to decide which algorithm among a set of possible choices is best,
• be able to prove correctness and analyze the running time of a given algorithm,
• be able to design efficient algorithms for new situations using the techniques learned,
• be able to prove a problem is NP-complete using reduction and understand the implications.

Major Topics

• Overview.
• Mathematical preliminaries.
• Sorting algorithms.
• Some useful data structures.
• Algorithm design and analysis techniques.
• Graph theory algorithms.
• Introduction to computational complexity .

Textbook

• Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press / McGraw-Hill, 2001.

Useful links

Graph theory

• graph glossary -- a nice reference.

Complexity

• complexity zoo -- a reference of complexity classes.