CPSC 536H - Empirical Algorithmics (Spring 2009)

[General Info] · [Course Outline] · [Paper reviews] · [Course Projects] · [Grading] · [Resources]

Latest news (04/15): As announced last week, there is a 'bonus' class this week, Thu, 16 April, 12:30-14:00 in DMP 101. Project presentations, 25min talks + 10min for discussion per group, have been scheduled for Wed, 22 April, 9:00-13:00, also in DMP 101.

Classes:
Tue, 15:30-17:30 in DMP 101
Wed, 16:30-17:30 in ICCS 206

Instructor:
   Holger H. Hoos
   E-mail: hoos "at" cs.ubc.ca
   Office: ICICS/CS complex, Room X541
   Office hour: Thu, 10:30-11:30 or by appointment

[Current official information on graduate courses in 2008/09 Term 2 can be found here]

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 and Basics
Module 2: Deterministic Decision procedures
Module 3: Randomised Decision Procedures
Module 4: Decision Procedures with Error
Module 5: Optimisation Procedures
Module 6: Algorithm Design

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.

(More information will be posted soon.)

If you have any questions regarding the course, please contact Holger (hoos@cs.ubc.ca).

Paper reviews

Paper reviews are conducted in groups of two students (no exceptions). They involve finding a paper relevant to the course material (either in terms of involving the empirical analysis of one ore more algorithms or in terms of offering alternative or additional methodology for such empirical analysis), summarising the content of the paper and describing how it relates to the course material, and critically assessing the empirical study or methodology used or proposed in the paper.

Paper proposals include a list of three papers along with a URL to an electronic version for each and a brief explanation how each of the papers relate to the course material. Proposed papers need to be published in a peer-reviewed venue and cannot involve the work of anyone at the UBC Department of Computer Science.

Paper reviews are expected to be roughly between 3 and 5 pages long.

Important dates (as discussed in class):

02/17, tue, 23:59:59 PST paper proposals due (via e-mail, in PDF format)

02/20, fri, 23:59:59 PST feedback on proposal + selection of paper

03/06, fri, 23:59:59 PST paper reviews due (vie e-mail, in PDF format)

Course projects

Course projects are conducted in groups of two students (no exceptions). They involve practical work in empirical algorithmics that clearly demonstrates proficiency with the methods and concepts covered in the course.

Project proposals are limited to 1 page of text (not counting references) and need to motivate and explain the proposed empirical study as well as explicitly state the goals of the study as well as a timeline including milestones and deliverables.

Project status updates are limited to 3 pages of text (not counting references, figures and tables) and need to clearly summarise the progress made so far (in relation to the milestones from the project proposal), summarise intermediate results, and indicate and justify any changes to the timeline from the proposal.

Final project reports are limited to 12 pages of text (not counting references, figure and tables), but can be shorter. They will be assessed like a submission to a scientific workshop, except that there will be less emphasis on novelty and relevance of the work, while technical soundness and readability will be weighed more heavily.

(Information on project presentations will be posted here and discussed in class towards the end of March.)

Important dates (as discussed in class):

02/25, wed, 23:59:59 PST groups formed (and communicated via e-mail to Holger)

03/06, fri, 23:59:59 PST project proposals due (vie e-mail, in PDF format)

03/24, tue, 23:59:59 PST project status updates due (vie e-mail, in PDF format)

04/10, fri, 23:59:59 PST final project reports due (vie e-mail, in PDF format)

mid-April project presentations (details TBA)

Grading

Final grades for this course will be determined based on the following three components: (1) A sizable course project (ca. 60%); (2) a paper review (ca. 25%); and (3) in-class participation (ca. 15%). The exact weighting of these components is at the discretion of the instructor and may be adjusted to reflect the overall degree to which a student has demonstrated proficient knowledge of the course material (please see course objectives and learning goals at the end of the lecture notes for each module).

Resources

Primary 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.
Automatic Algorithm Configuration based on Local Search.
Frank Hutter, Holger H. Hoos and Thomas Stützle - Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07), pp. 1152-1157, 2007. (get PDF file - 176k)
SATzilla: Portfolio-based Algorithm Selection for SAT
Lin Xu, Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown - Journal of Artificial Intelligence Research, Volume 32, pp. 565–606, 2008. (abstract and electronic version - Open Access)

Supplementary literature

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]
D. J. Sheskin: Handbook of Parametric and Nonparametric Statistical Procedures, second edition. Chapman & Hall / CRC, Boca Raton, Florida, USA, 2000. [excellent in-depth treatment on statistical hypothesis tests and their proper application]
W. J. Conover: Practical Nonparametric Statistics, third edition. John Wiley & Sons, New York, NY, USA, 1999. [more specialised introduction to non-parametric statistics]

(This list will be extended throughout the term.)

Lecture notes:

Module 1: [ get text file - 11KB ]
Module 2: [ get text file - 20KB ]
Module 3: [ get text file - 12KB ]
Module 4: [ get text file - 10KB ]
Module 5: [ get text file - 13KB ]

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 ]
Useful commands in R: [ get text file - 3.4KB ]

last update 09/04/15, hh

	02/17, tue, 23:59:59 PST	paper proposals due (via e-mail, in PDF format)
	02/20, fri, 23:59:59 PST	feedback on proposal + selection of paper
	03/06, fri, 23:59:59 PST	paper reviews due (vie e-mail, in PDF format)

	02/25, wed, 23:59:59 PST	groups formed (and communicated via e-mail to Holger)
	03/06, fri, 23:59:59 PST	project proposals due (vie e-mail, in PDF format)
	03/24, tue, 23:59:59 PST	project status updates due (vie e-mail, in PDF format)
	04/10, fri, 23:59:59 PST	final project reports due (vie e-mail, in PDF format)
	mid-April	project presentations (details TBA)