Analysis of algorithms as a teaching experience

The author of this paper has a quite long research and teaching experience in the context of the analysis of algorithms, as popularized by Knuth and Sedgewick and Flajolet; this approach to the analysis of algorithms concentrates on precisely characterizing the performance of algorithms by determining their best, worst and average case performance using a methodology that can be refined to produce increasingly precise answers when desired. The Analysis of Algorithms teaching experience concerns the Computer Science degree at the University of Florence and, in general, involves students more interested in the implementation of an algorithm than in the corresponding theoretical aspects. A compromise that was successful over the years consists in teaching students the analytical aspects of the analysis of an algorithm and then asking them to implement the algorithm in order to precisely check the theoretical results. This is in general possible for small sizes of the problem under consideration while for larger sizes it is necessary to set up a simulation by executing the algorithm on a sufficiently large sample of inputs. In this latter case, obviously, the theoretical results cannot be checked precisely and some statistical test must be used to conclude that the simulation agrees with the theory. In other words, during the course, the analysis of an algorithm or a data structure is accompanied by its simulation with a system of symbolic computation, like Maple.