A Review of Teaching and Learning through Practice of Optimization Algorithms

Introduction

Curricular recommendations for Computer Science (CS) date back to the late sixties (ACM, 1968). Although subsequent recommendations gave some importance to laboratories, it was not completely recognized until the writing of the Denning Report (Denning, Comer, Gries, Mulder, Tucker, Turner & Young, 1989). The Report argued for a multidisciplinary nature of CS based on three different knowledge traditions: mathematics, engineering and science. In particular, the scientific tradition deals with the study of artifacts using the scientific method and experimentation. Laboratories and experimentation attracted the attention in the following years (McCracken, 1989) and since experimentation has attracted the focus now and then (Tichy, 1998; Denning, 2007). Remarkably, some proposals make explicit the relation between experimentation with algorithms and the scientific method (Baldwin, 1992; Matocha, 2002). Some instructors have addressed this issue from a pragmatic point of view for an algorithms course (Sanders, 2002) and even throughout the CS curriculum (Braught, Reed & Miller, 2004; Reed, Miller & Braught, 2000).

Experimentation has probably received the most attention in the field of algorithms. This preeminence is probably due to the fact that algorithms have a clear definition (amenable to formal specification), have well-defined properties, and are small-scale artifacts. Most proposals include experimenting with the running time of different sorting algorithms as well as experimenting with other measures and algorithms. Almost all of these experiences deal with the algorithmic property of efficiency. In addition, we find some experimentation in programming courses, here related to the property of correctness. Experimenting with correctness is called testing. A new instructional approach has recently emerged based on testing, called test-driven development (Shepard, Lamb & Kelly, 2001). We do not deepen here into these forms of experimentation, but the interested reader is referred elsewhere (Velázquez-Iturbide, Pareja-Flores, Debdi & Paredes-Velasco, 2012). Note also that experimentation does not necessarily play an opposite role to formal proofs, but both approaches may complement each other (Coffey, 2013).

The purpose of this chapter is addressing a third property of many algorithms, namely optimality. This property is a variant of correctness which only makes sense for optimization problems. A part of the specification of optimization problems states that not only the solution must be valid, but it must also be optimal (with respect to a given measure). Although not such a general property as correctness or efficiency, optimization also is important in algorithmics. Many of the most interesting algorithms are optimization algorithms. Many of the theoretical results about computational complexity involve optimization problems. Several of the most commonly used algorithm design techniques address optimization problems, either exactly or approximately. We are interested in the different issues around practice and experimentation as an approach to teaching optimization algorithms. We do not include here any definitions of algorithms, but the reader is referred to well-known textbooks, e.g. Brassard and Bratley (1996), Cormen, Leiserson, Rivest and Stein (2009), or Sahni (2005).