A Review of Teaching and Learning through Practice of Optimization Algorithms

A Review of Teaching and Learning through Practice of Optimization Algorithms

J. Ángel Velázquez-Iturbide (Universidad Rey Juan Carlos, Spain), Ouafae Debdi (Universidad Rey Juan Carlos, Spain) and Maximiliano Paredes-Velasco (Universidad Rey Juan Carlos, Spain)
DOI: 10.4018/978-1-4666-7304-5.ch004
OnDemand PDF Download:
$37.50

Abstract

Algorithmics is an important core subject matter in computer science education. In particular, optimization algorithms are some of the most difficult to master because their problem statement includes an additional property, namely optimality. The chapter contains a comprehensive survey of the teaching and learning through practice of optimization algorithms. In particular, three important issues are reviewed. Firstly, the authors review educational methods which partially or completely address optimization algorithms. Secondly, educational software systems are reviewed and classified according to technical and educational criteria. Thirdly, students' difficulties and misunderstandings regarding optimization algorithms are presented. The chapter intends to consolidate current knowledge about the education of this class of algorithms for both computer science teachers and computer science education researchers.
Chapter Preview
Top

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).

Complete Chapter List

Search this Book:
Reset