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.

COS 554 is the graduate version of this course, which shares most class meetings and coursework with the undergraduate version (COS 454) but that includes additional coursework and is assessed to a higher standard.

News and Reminders:

• Please read the newsgroup for timely announcements:
  Local group umaine.cos350 on NNTP server creak.um.maine.edu.
  Web interface: http://chaw.eip10.org/news/. An email message with authentication information and other details was sent to all registered students on 2021-01-24. In case it was not received, please contact the instructor.
• Please use the PDF version of this document for printing and reference: cos454.pdf
• The most recent version of this document may be found at http://chaw.eip10.org/cos454/.
• Some sections below point to material in separate documents that are found on the class Web site, linked from the online version of this document.
• Until recently, this course was numbered as COS 350. Please bear this in mind when referring to or searching for older material.¹

© 2021 Sudarshan S. Chawathe
Validated HTML 4.01 Transitional. Check.