AlgLab Home

Readings in Experimental Algorithmics

Consult the list below learn more about many of the topics covered in the Guide to Experimental Algorithmics.

These resources present many examples of experimental work in algorithm design and analysis.

ACM Journal on Experimental Algorithmics, published by the Association for Computing Machinery.
INFORMS Journal on Computing, published by the Operations Research Society.
DIMACS Implementation Challenges, sponsored by DIMACS. Workshop Proceedings are published by the American Mathematical Society in the DIMACS Series in Discrete Mathematics and Theoretical Computer Science
Proceedings of the Workshop on Algorithm Engineering (WAE). In 2002 this workshop became the Engineering and Applications Track of the European Symposium on Algorithms (ESA).
Proceedings of the Workshop on Algorithm Engineering and Experimentation (ALENEX), sponsored by SIAM.
Proceedings of some Dagstuhl Seminars on Experimental Algorithmics have been published in the Springer LNCS Series, numbers: 2547, 5971.
Proceedings of the Symposium on Experimental Algorithms (SEA), formerly the Workshop on Excperimental and Efficient Algorithms (WEA). Proceedings are published in the Springer LNCS series, numbers: 2647, 3059, 3503, 4007, 5038, 5526, 6049, and 6630.

Articles on experimental methodology for algorithmic problems, aimed a particular audiences.

Ian Gent Stuart A. Grant, Ewen MacIntyre, Patrick Prosser, Paul Shaw, and Barbara M. Smith, How Not to Do It, University of Leeds School of Computer Studies, Research Report Series, Report No. 97.25, May 1997. An entertaining account of pitfalls of algorithmic experiments and how to avoid them.
David S. Johnson, ``A theoretician's guide to the experimental analysis of algorithms,''in M. H. Goldwasser, D. S. Johnson, and C. C. McGeoch, eds., Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth Implementation Challenges, AMS, pp. 215-250 , 2002. Pet peeves and pitfalls of conducting and reporting experimental research on algorithms, aimed at the theoretician.
Thomas Bartz-Beielstein, M. Chiarandini, Luis Paquette, and Mike Preuss, Eds. Experimental Methods for the Analysis of Optimization Algorithms, Springer, 2010. Contributions by several authors, aimed at graduate students and researchers, emphasizing statistical analysis and heuristics for optimization problems.
Matthias M\:{u}ller-Hanneman and Stefan Schirra, Eds., Algorithm Engineering: Bridging the Gap Between Algorithm Theory and Practice, Lecture Notes in Computer Science, Vol 5971, Springer, 2010. Contributions and tutorial discussions of topics in algorithm engineering, aimed at researchers and graduate students.

Online articles and resources on tuning algorithms and code for faster computation times.

Derek Atkins, Michael Graff, Arjen K. Lenstra, and Paul C Leyland, ``The Magic Words are Squeamish Ossifrage,'' proceedings of ASIACRYPT '94 pp. 263-277, 1994. Describes how they found a factor of 4-quadrillion speedup in their code to solve an encryption problem.
Bernard M. E. Moret and Tandy Warnow, ``Reconstructing Optimial Phylogenetic Trees: A Challenge in Experimental Algorithmics,'' in R. Fleischer et al, eds. Experimental Algorithmics, LNCS 2547, p. 163-180, 2002. Illustrating algorithm tuning and code tuning techniques yielding speedups by factors as high as 200,000.
Jon Louis Bentley, ``Faster and Faster Yet,'' Unix Review, June 1997. Improving the runtime of an exhaustive search algorithm from eons to minutes. (Hard to locate: try a web search.)
Jon Louis Bentley, ``Part II: Performance'' Chapters 6-10 in Programming Pearls Second Edition, ACM Press and Addison Wesley, 2000.
Brian W. Kernighan and Rob Pike, ``Chapter 7: Performance'' in The Practice of Programming Addison Wesley, 1999.
Matthias Mueller-Hanneman and Stefan Schirra, Eds., Algorithm Engineering: Bridging the Gap Between Algorithm Theory and Practice, Lecture Notes in Computer Science, Vol 5971, Springer, 2010. Chapters 5 and 6 discuss algorithm and code tuning.
Jack Shirazi, Java Performance Tuning, O'Reilly 2000. Many of tuning tips herein are language-independent.

Paul Cohen, Empirical Methods for Artificial Intelligence, MIT Press 1995. A data analysis textbook with many illustrations from experiments on heuristics.
Paul Bratley, Bennett L. Fox, Linus E. Schrage, A Guide to Simulation, Second Edition Springer-Verlag, 1987. A textbook on discrete event simulation, with several topics of interest to algorithmic problems, such as variance reduction techniques, random number generation, an analysis of horizon effects.
John M. Chambers, William S. Cleveland, Beat Kleiner, and Paul A. Tukey, Graphical Methods for Data Analysis, Wadsworth and Brooks/Cole Statistics/Probability Series, 1983.
See also relevant chapters in the books by Mueller-Hanneman and Shirra, and by Bartz-Beielstein and by Thomas Bartz-Beielstein et al., listed above.

Ian Sanders, Teaching empirical analysis of algorithms, Ian Sanders, in Proceedings of the 33rd SIGSCE Technical Symposium on Computer Science Education, 2002, and in ACM SIGSE Bulletin - Inroads, Vol 24 Issue 1, March 2002.
Catherine C. McGeoch and Bernard M. E. Moret, ``How to Present a paper on experimental work with algorithms,'' SIGACT News Vol 30, No. 4, pp. 85-90, 1999.
For the graduate student planning to give a conference talk.
Catherine C. McGeoch, ''Experimental Algorithmics for Undergraduates'', presented at the Workshop on Experimental Computer Science, part of ACM FCRC, June 2007.
Syllabus: Georgia Tech CS 6140: Computational Science & Engineering (CSE) Algorithms
Amherst College CS34 Applied Algorithms(2010)
Experimental Algorithms Projects used in courses:
Sorting Project Computer Science 20: Data Structures and Algorithms I (Fall 2010), Amherst College.
Divide and Conquer Project, Computer Science 20: Data Structures and Algorithms I (Fall 2010), Amherst College.
Assignment Experiments to compare average case and typical case costs of binary search, Data Structures and Algorithms 2 (Spring 2010), Amherst College.