Traditional undergraduate algorithms instruction focuses primarily on the formal analysis of worst case performance. We present here a methodology that supplements traditionally-taught topics with experimental explorations of algorithms. Such supplementation can either be as a part of a traditional algorithms course or in an additional project-oriented course. Our projects invite students to implement a variety of algorithms, run benchmarks on their implementations with randomly-generated inputs, plot their results, compare alternative implementations, and draw conclusions. In this paper, we characterize projects that address three distinct questions of algorithm analysis: (1) What is an algorithm’s running time? (2) How well does an algorithm achieve an optimization goal? and (3) How can we use algorithms to test models of the real world? We believe this approach yields some surprising insights not readily apparent from formal analysis and provides students with experiential evidence for the importance of good algorithms. The skills learned and practiced in such projects should appeal to a variety of computer science students with varying desired career paths. We give results from our own course experience with such projects and we also provide recommendations for teaching similar topics in a modular fashion, leaving programming language and specific topic choices to an instructor’s discretion.
(joint work with 3 Mikes: Dillencourt, Goodrich, and Shindler)
Video of the talk