Experimentation with optimization problems in algorithm courses

Algorithms are one of the core elements in computer science curricula. They involve design and analysis activities, mainly analysis of correctness and efficiency. A property which has received less attention is optimality. In order to gain insight and skills on optimization, and to promote active learning, we proposed an experimental method assisted by interactive assistants. In this paper we give a detailed account of how to use the experimental method in an algorithm course. Firstly, we show how to use it with greedy algorithms, with equivalent selection functions as the most interesting issue. Secondly, we use the method to demonstrate the need of other algorithm design techniques (e.g. dynamic programming) to solve other problems. Thirdly, nearly-optimal selection functions can be used as an introduction to approximation algorithms (i.e. heuristics).