605.421.34 Foundations of Algorithms

Whiting School of Engineering
The Johns Hopkins University
Fall 1977, Spring 1988

by Z. George Mou

Algorithms are procedures that computers follow to solve certain problems. The purpose of this course is to familiarize the students with the established algorithms, and, more importantly, teach the students the methodology by which new algorithms can be devised. Among the paradigms that we examine in the class are divide-and-conquer, greedy algorithms, dynamic programming, and branch-and-bound. Each of the paradigms will be illustrated with a number of representative algorithms. We also go beyond the individual paradigms and establish the inter-connections between these paradigms. The validation and complexity analysis, which address the issues of if and how efficiently an algorithm solves a given problem, will be an important component of this course. The students are expected to learn not only the results but also the methods in this area. Related notions such as lower bounds and completeness of problems will be covered. The fast-growing parallel and distributed computing technology calls for a treatment on parallel algorithms. Unlike the textbook which organizes the materials by architectures, we will present the algorithms by paradigms. The mappings of the algorithms to network topologies including mesh and hypercubes will be presented separately.

Evaluation:

Homework 50%, Midterm 20%, Final 30%.

Prerequisite:

C, C++, or Java

Textbook:

Introcution to Algorithms, T. Cormen, C. Leiserson, and R. Rivest, MIT Press, 1985.

References:

[1] Sedgewick, Algorithms in C++, Addison Wesley, 1992 [2] Stanley Lippman, C++ Primer, Addison Wesley, 1992 [3] Horiwitz, Fundamentals of Data Structures in C++, Computer Science Press, 1995 [4] Gary and Johnson, Computers and Intractability, Freeman, 1979 [5] Horold Stone, High Performance Computer Architecture, Addison-Wesley, 1987. [6] Horowitz, et. al, Computer Algorithms C++, Computer Science Press, 1997

Go back up.