CPS 230
Fall 2005

The Design and Analysis of Algorithms

This course introduces a number of algorithms that are theoretically interesting and practically important. It also discusses design paradigms, such as randomization and dynamic programming, and analysis techniques, probabilistic analysis and amortization.

• Herbert Edelsbrunner
  Office: D203 LSRC Bldg
  Email: edels@cs.duke.edu
  Office hours:

• Design Techniques
• Searching
• Prioritizing
• Graph Algorithms
• Network Flow
• String Algorithms
• NP-Completeness

There will be handouts and lecture notes avaliable after class. The main text used in this course is

• Tarjan, Data Structures and Network Algorithms, SIAM, 1983.

Recommended References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, 2nd Edition, McGraw Hill, Boston, 2001.
• Graham, Knuth and Patashink, Concrete Mathmatics. A Foundation for Computer Science, Addison Wesley, 1988.