A unified framework to experiment with algorithm optimality and efficiency

It is common in algorithm courses to assess the correctness of algorithms via testing as well as conducting experiments to measure their run-time performance. However, two severe problems must be addressed: both activities are conducted using different procedures and tools, and algorithm assessment systems do not support well optimization problems due to their unique characteristics. Given the relevant role of optimization algorithms in computing, we present a unified framework to support experimentation with both criteria, i.e., optimality and efficiency. The contributions of the article are two-fold. Firstly, we present a unified framework to experiment with both criteria, by using explicit principles and by presenting its instantiation in the AlgorEx system. The homogeneous treatment of optimality and time efficiency contributes to smoother integration of experimentation into a course syllabus and to easier adoption of the system. Secondly, we present our experience in several academic years in an algorithms course. Initially, it was noticed that students had severe difficulties to deal with experimentation, but their academic performance sharply increased by fully integrating experimentation along the complete course. The article also identifies some opportunities for extension in AlgorEx