This course is an introduction to algorithms. Data structures play an important role, both in enabling efficient algorithms and in using others for their own implementation. Topics include the analysis of algorithms (analytical and experimental), algorithm design techniques (such as dynamic programming), advanced data structures (such as Fibonacci heaps), algorithms for specific problems (such as shortest paths in graphs, and string matching), and an introduction to NP completeness and related topics. An important theme is abstraction and its application to programming.
Prerequisites: COS 226 (data structures); COS 250 (discrete structures); programming maturity.