CPSC 536H - Empirical Algorithmics (Spring 2008)

[General Info] · [Course Outline] · [Resources]

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.)

Classes:
Tue+Thu, 14:00-15:30 in ICCS 238
First class: Tue, 2006/01/08

Instructor:
   Holger H. Hoos
   E-mail: hoos "at" cs.ubc.ca
   Office: ICICS/CS complex, Room X541
   Office hour: Tue, 11:30-12:30

Course objectives:

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).

Prerequisite knowledge: Algorithms, basic knowledge of statistics

Topics covered in this course include:

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

... and a selection of the following topics:

multi-objective optimisation
automated algorithm configuration and parameter tuning
automated algorithm selection
self-tuning mechanisms
algorithm engineering

Preliminary course outline

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)

Note: 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.

Resources

Literature

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.]

(This list will be extended throughout the term.)

Lecture notes:

Module 1: [ get text file - 9KB ]
Module 2: [ get text file - 19KB ]
Module 3: [ get text file - 12KB ]
Module 4: [ get text file - 9KB ]
Module 5: [ get text file - 13KB ]
Extra: multi-objective optimisation algorithms, experimental design [ get text file - 7KB ]

Slides (as used in class):

Some introductory material (class 1): [ get PDF version - 23KB ]
Excerpts from Laughlin interview (class 2): [ get PDF version - 61KB ]
Module 2: [ get PDF version - 122KB ]
Module 3: [ get PDF version - 526KB ]
Module 4: [ get PDF version - 49KB ]
Module 5: [ get PDF version - 104KB ]

Other materials:

CPU timing C++ code from Module 2: [ get zip file - 1.3KB ]
Data and scripts for scaling case study from Module 2: [ get zip file - 3.2KB ]

last update 08/04/14, hh