Abstract
Experimental Algorithmics is concerned with the design, implementation, tuning, debugging and performance analysis of computer programs for solving algorithmic problems. It provides methodologies and tools for designing, developing and experimentally analyzing efficient algorithmic codes and aims at integrating and reinforcing traditional theoretical approaches for the design and analysis of algorithms and data structures.
In this paper we survey some relevant contributions to the field of Experimental Algorithmics and we discuss significant examples where the experimental approach helped in developing new ideas, in assessing heuristics and techniques, and in gaining a deeper insight about existing algorithms.
This work has been partially supported by the European Commission (Project ALCOM-FT), by the Italian Ministry of University and Scientific Research (Project “Algorithms for Large Data Sets: Science and Engineering”) and by CNR, the Italian National Research Council.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A.V. Aho, J.E. Hopcroft, and J.D. Ullman. The Design and Analysis of Computer Algorithms. Addison Wesley, 1974.
R.K. Ahuia, T.L. Magnanti, and J.B. Orlin. Network Flows: Theory, Algorithms and Applications. Prentice Hall, Englewood Cliffs, NJ, 1993.
R. Anderson. The role of experiment in the theory of algorithms. In Proceedings of the 5th DIMACS Challenge Workshop, 1996. Available over the Internet at the URL: http://www.cs.amherst.edu/dsj/methday.html.
C. Berge and A. Ghouila-Houri. Programming, Games and Transportation Networks. Wiley, 1962.
G. Bilardi, P. D’Alberto, and A. Nicolau. Fractal matrix multiplication: a case study on portability of cache performance. Manuscript, May 2000.
M.H. Brown. Algorithm Animation. MIT Press, Cambridge, MA, 1988.
M.H. Brown. Zeus: a System for Algorithm Animation and Multi-View Editing. In Proceedings of the 7-th IEEE Workshop on Visual Languages, pages 4–9, 1991.
G. Cattaneo, U. Ferraro, G.F. Italiano, and V. Scarano. Cooperative Algorithm and Data Types Animation over the Net. In Proc. XV IFIP World Computer Congress, Invited Lecture, pages 63–80, 1998. System Home Page: http://isis.dia.unisa.it/catai/.
B.V. Cherkassky. A Fast Algorithm for Computing Maximum Flow in a Network. In A.V. Karzanov editor, Collected Papers, Issue 3: Combinatorial Methods for Flow Problems, pages 90–96. The Institute for Systems Studies, Moscow, 1979. In Russian. English translation appears in AMS Translations, Vol. 158, pp. 23–30. AMS, Providence, RI, 1994.
B.V. Cherkassky and A.V. Goldberg. On implementing the push-relabel method for the maximum flow problem. Algorithmica, 19:390–410, 1997.
T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. The MIT Press, 1990.
P. Crescenzi, C. Demetrescu, I. Finocchi, and R. Petreschi. Reversible Execution and Visualization of Programs with LEONARDO. Journal of Visual Languages and Computing, 11(2), 2000. Leonardo is available at the URL: http://www.dis.uniroma1.it/~demetres/Leonardo/.
G.B. Dantzig. Application of the Simplex Method to a Transportation Problem. In T.C. Hoopmans editor, Activity Analysis and Production and Allocation, Wiley, New York, 1951.
Demetrescu, C. and Finocchi, I. Break the “Right” Cycles and Get the “Best” Drawing. In Proc. of the 2nd International Conference on Algorithms and Experimentations (ALENEX’00) San Francisco, CA, 2000.
M. Eisenstadt and M. Brayshaw. The transparent prolog machine: An execution model and graphical debugger for logic programming. Journal of Logic Programming, 5(4):1–66, 1988.
A.V. Goldberg. Selecting problems for algorithm evaluation. In Proc. 3-rd Workshop on Algorithm Engineering (WAE’99), LNCS 8, pages 1–11, 1999.
A.V. Goldberg and B.M.E. Moret. Combinatorial algorithms test sets [CATS]: The ACM/EATCS platform for experimental research (short). In SODA: ACM-SIAM Symposium on Discrete Algorithms, 1999.
R.R. Henry, K.M. Whaley, and B. Forstall. The University of Washington Program Illustrator. In Proceedings of the ACM SIGPLAN’90 Conference on Programming Language Design and Implementation, pages 223–233, 1990.
D. Johnson. A theoretician’s guide to the experimental analysis of algorithms. In Proceedings of the 5th DIMACS Challenge Workshop, 1996. Available over the Internet at the URL: http://www.cs.amherst.edu/dsj/methday.html.
D. Klingman, A. Napier, and J. Stutz. Netgen: A program for generating large scale capacitated assignment, transportation, and minimum cost network flow problems. Management Science, 20:814–821, 1974.
Donald E. Knuth. Stanford GraphBase: A platform for combinatorial algorithms. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 41–43, New York, NY 10036, USA, 1993. ACM Press.
S.P. Lahtinen, E. Sutinen, and J. Tarhio. Automated Animation of Algorithms with Eliot. Journal of Visual Languages and Computing, 9:337–349, 1998.
T. Leong, P. Shor, and C. Stein. Implementation of a combinatorial multicommodity flow algorithm. In D.S. Johnon and C. McGeoch, eds., Network Flows and Matching: First DIMACS Implementation Challenge, pages 387–406, 1993.
C. McGeoch. A bibliography of algorithm experimentation. In Proceedings of the 5th DIMACS Challenge Workshop, 1996. Available over the Internet at the URL: http://www.cs.amherst.edu/dsj/methday.html.
K. Mehlhorn and S. Naher. LEDA, a platform for combinatorial and geometric computing. Communications of the ACM, 38:96–102, 1995.
B.M.E. Moret. Towards a discipline of experimental algorithmics. In Proceedings of the 5th DIMACS Challenge Workshop, 1996. Available over the Internet at the URL: http://www.cs.amherst.edu/dsj/methday.html.
B.M.E. Moret and H.D. Shapiro. An empirical assessment of algorithms for constructing a minimal spanning tree. Computational Support for Discrete Mathematics N. Dean and G. Shannon eds. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 15:99–117, 1994.
G.C. Roman, K.C. Cox, C.D. Wilcox, and J.Y Plun. PAVANE: a System for Declarative Visualization of Concurrent Computations. Journal of Visual Languages and Computing, 3:161–193, 1992.
S. Skiena. Who is interested in algorithms and why? lessons from the stony brook algorithms repository. In Proc. Workshop on Algorithm Engineering (WAE’98), pages 204–212, 1998.
J.T. Stasko. The Path-Transition Paradigm: a Practical Methodology for Adding Animation to Program Interfaces. Journal of Visual Languages and Computing, 1(3):213–236, 1990.
J.T. Stasko. A Methodology for Building Application-Specific Visualizations of Parallel Programs. Journal of Parallel and Distributed Computing, 18:258–264, 1993.
J.T. Stasko, J. Domingue, M.H. Brown, and B.A. Price. Software Visualization: Programming as a Multimedia Experience. MIT Press, Cambridge, MA, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Demetrescu, C., Italiano, G.F. (2000). What Do We Learn from Experimental Algorithmics?. In: Nielsen, M., Rovan, B. (eds) Mathematical Foundations of Computer Science 2000. MFCS 2000. Lecture Notes in Computer Science, vol 1893. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44612-5_3
Download citation
DOI: https://doi.org/10.1007/3-540-44612-5_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67901-1
Online ISBN: 978-3-540-44612-5
eBook Packages: Springer Book Archive