Foundations of Algorithms
605.421

Course Description
This follow-on course to data structures (e.g., 605.202) provides a survey of computer algorithms and examines fundamental techniques in algorithm design and analysis. Topics include advanced data structures (red-black and 2-3-4 trees), recursion and induction, algorithm analysis and computational complexity (recurrence relations, big-O notation), sorting and searching, string processing (Boyer-Moore, Knuth-Morris-Pratt, and pattern matching), graph algorithms (depth-first and breadth-first search, connectivity, union-find, minimum spanning trees, and network flow), and computational geometry (points, lines, polygons, and convex hull). Selected advanced topics (dynamic programming and NP-complete problems) are also introduced. Grading is based on problem sets, programming projects, and examinations.

Prerequisites
Working knowledge of data structures and Java, C++, or C.

Instructor
William Lew is Senior Technical Assistant Director with the U.S. General Accounting Office Computer Information Technology Assessment Group. Dr. Lew's areas of research interest include probability theory, algorithmic analysis, databases, and networking & communications.

Textbook
Introduction to Algorithms, (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest), McGraw-Hill, 1993.

Additional Course Information

Return to Computer Science Courses | Computer Science  | Part-Time Engineering

Spring 1999-2000