Part-Time Programs in Engineering and Applied Science, Johns Hopkins University
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.

Information Available for Currently Enrolled Students

Syllabus

  1. What is Algorithm Analysis?
  2. Mathematics for Algorithm Analysis
  3. Recurrences
  4. Probabilistic Analysis and Randomized Algorithms
  5. NP-Completeness & Approximation Algorithms
  6. Sorting
  7. Medians and Order Statistics
  8. Hash Tables, Binary Trees, Red-Black Trees, and Augmenting Data Structures
  9. Dynamic Programming & Greedy Algorithms
  10. Amortized Analysis
  11. Basic Graph Algorithms and MST Algorithms
  12. Shortest Path Algorithms
  13. Matrix Operations
  14. String Matching
Prerequisites
Working knowledge of data structures and Java, C++, or C.

Instructor
John Boon is a part-time operations researcher for RAND and the proprietor of Intelligent Information Analysis, a consulting firm providing integrated mathematics and computer science services. Mr. Boon's areas of expertise are operations research, advanced statistical analysis, systems analysis, and software engineering. Mr. Boon earned undergraduate degrees in mathematics and political science from Virginia Wesleyan College and a M.S. in operations research from the George Washington University. He was a tenured faculty member at another college prior to returning to corporate employment. Mr. Boon has taught graduate courses since 1988.

Course Section, Location, and Time
Please refer to the Course Schedule for section information, including time and location.

Computer Lab Requirements
Students must be proficient in either Java or C++. Students must have an email address and must make that address known to the course instructor as soon as practical after the start of the course. Students may use their own computing resources (hardware/software tools) or may arrange to access the necessary tools through the student services entities of JHU. Class examples will be compiled and processed with Java 2 (JDK 1.3.1) and the GNU port of gcc for 32-bit Windows version 2.95.3. The GNU port of the gcc 32-bit Windows tools can be obtained from http://www.delorie.com. Students must have access to the Internet, have a web browser and the Acrobat Reader application.

Textbook
Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, McGraw-Hill, 2001 (ISBN 0-07-013151-1)

Introduction to Algorithms, Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, MIT Press, 2001 (ISBN 0-262-03141-8)

Dr. Dobb's Essential Books on Algorithms and Data Structures, Release 2 (CD-ROM)
 (9 books including First Edition of the course text book)

Return to Part-Time Engineering
Return to Whiting School of Engineering
Return to JHUniverse