CPSC 536H - Empirical Algorithmics (Spring 2008)
[General Info] ·
[Course Outline] ·
Latest news (04/14):
The deadline for handing in final project reports
has been extended to
Tue, 22 April, 23:59:59 PDT. (Max 10 pages + references + figures,
in PDF format via e-mail.)
in ICCS 238
First class: Tue, 2006/01/08
Holger H. Hoos
E-mail: hoos "at" cs.ubc.ca
Office: ICICS/CS complex, Room X541
Office hour: Tue, 11:30-12:30
Algorithms, basic knowledge of statistics
- To understand basic issues related to Computer Science as an empirical science.
- To be capable of using the scientific method for the empirical analysis of algorithms.
- To be capable to apply basic and advanced empirical methods for the design and analysis
of algorithms (with an emphasis on heuristic algorithms that are inaccessible
to analytical methods).
Topics covered in this course include:
... and a selection of the following topics:
- goals and challenges of empirical analysis of algorithms
- design of computational experiments
- benchmark selection
- statistical analysis and significance tests
- decision and optimisation problems
- deterministic and randomized algorithms (with and without error)
- run-time vs solution quality / error trade-off
- scaling and robustness analysis
- parallelisation and restart techniques
- algorithm portfolios
- multi-objective optimisation
- automated algorithm configuration and parameter tuning
- automated algorithm selection
- self-tuning mechanisms
- algorithm engineering
Preliminary course outline
The course will consist of three components: (1) regular classes,
(2) paper presentations (by participants) and discussions, and (3) a sizeable course project.
Most of the advanced topics will be covered based on paper presentations
and selected based on the interests of the participants.
Course projects can be related to the student's research interests / thesis topic
and are determined in consultation with the instructor.
- Module 1: Introduction
- Module 2: Deterministic algorithms for decision problems
- Module 3: Randomised algorithms without error (Las Vegas algorithms) for decision problems
- Module 4: Randomised algorithms with error (Monte Carlo algorithms) for decision problems
- Module 5: Algorithms for optimisation problems
- Module 6: Advanced topics (TBD)
(This list will be extended throughout the term.)
- Paul R. Cohen: Empirical Methods for Artificial Intelligence. MIT Press, 1995.
- Chapter 4 of H.H.Hoos and T.Stützle: Stochastic Local Search - Foundations and Applications. Morgan Kaufmann / Elsevier 2004.
- D.S.Johnson: A Theoretician's Guide to the Experimental Analysis of Algorithms.
In: Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges, M. H. Goldwasser, D. S. Johnson, and C. C. McGeoch, Editors, American Mathematical Society, Providence, 2002, 215-250.
- D.L. Applegate, R.E. Bixby, V. Chvátal & W.J. Cook: The Traveling Salesman Problem
- A Computational Study. Princeton University Press, 2006.
[Used scaling data from Ch.15, pp.494ff. for case study in Module 2.]
Slides (as used in class):
last update 08/04/14, hh