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
John Sadowsky

Additional Course Information

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

Fall 99-2000