9450948 Simonson An experimental algorithms analysis lab is proposed. It will be used to support a newly designed Algorithms and Complexity course. The new course integrates theory of algorithms with software design in an experimental setting; and thereby follows the philosophy of the new ACM/IEEE curriculum guidelines: "to integrate the processes of theory, abstraction and design into each course and reinforce them with laboratory work." AI91 The typical course in algorithms does not include an experimental component. The introduction of such a component is natural and serves to clarify the theory, as well as to develop the students' skills in software design. Each algorithm motivates a number of different experimental software projects. These include: the development of an environment (often graphics-based) in which to generate test data and measure the algorithm's performance on special inputs; the design of a system to experiment with variations of the algorithm which defy precise analysis; and the implementation of an appropriate graphical user interface to interact with the algorithm. The software environment, in turn, motivates the discovery of new algorithms and theorems. Experimenting with hard to analyze algorithms helps formulate hypotheses about the algorithm's correctness and complexity. The lab allows students to play in the sandbox of algorithms, measure things, make conclusions and discover new ideas. The algorithms are the motivation for the software design, and the software serves as a tool to learn about algorithms. In each lab, students design software to empirically study the complexity of an algorithm, explore a new variation of an algorithm, or experiment with methods of taming an NP-Complete problem. The students design an environment that will let them experiment in the most productive way. Often weaker students with better designed tools can succeed faster with their Conjectures and conclu sions than bright students with poorly designed tools. The lab will also be used for honors theses, and our new general studies course for non-majors, Talking to Machines.
