Foundations of Algorithms
605.421.72
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.
Syllabus
- What is Algorithm Analysis?
- Mathematics for Algorithm Analysis
- Summations, Recurrences, Probability
- Sorting, Medians, and Order Statistics
- Hash Tables, Binary Trees, Red-Black Trees, and Augmenting Data Structures
- Dynamic Programming, Greedy Algorithms
- Amortized Analysis, B-Trees, Disjoint Sets
- Basic Graph Algorithms and MST Algorithms
- Shortest Path Algorithms
- Maximum Flow Algorithms
- String Matching
- NP-Completeness and Approximation Algorithms
- Search Heuristics for NP-Complete Problems
- Metaheuristics, Systems of Algorithms
Prerequisites
Prerequisites: Working knowledge of data structures and Java, C++, or C.
Instructor
Dr. Hollywood is an associate analyst for the RAND Corporation, where he studies adaptive, multilevel control architectures for distributed computing networks. As part of this research, he designs and tests various types of control algorithms, including resource-allocation algorithms and job scheduling algorithms. He also has worked as a consultant to a dot-com company, developing data structures and algorithms relevant to a consumer purchasing application. Dr. Hollywood has a Ph.D. in Operations Research from the Massachusetts Institute of Technology.
Course Section, Location, and Time
Please refer to the Course Schedule
for section information, including time and location.
Computer Lab Requirements
No specific computer requirements are necessary for this course.
Textbook
by
Return to Part-Time Engineering
Return to Whiting School of Engineering
Return to JHUniverse