CPSC 536H - Empirical Algorithmics (Spring 2012)

Classes:
   Tue+Thu, 11:00-13:30 in ICCS 104
   First class: Thu, 2012/01/05

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

What this course is about and why you might want to take it:

In a nutshell, it is about principled empirical methods for studying the performance and behaviour of algorithms that cannot be analysed using techniques from computational theory, and for building algorithms that perform well in practically interesting situations. These empirical methods are firmly grounded in established techniques from statistics, optimisation and machine learning, and they are being used increasingly widely and with great success in many areas of computing science and its applications. In particular, they play an increasingly prominent role in the development of state-of-the-art algorithms for solving a wide range of so-called NP-hard problems, which arise in many areas of computing science and its applications, including hardware design, software engineering, electronic commerce, manufacturing, genome sequencing and molecular structure prediction.

So ... you want to conduct proper computational experiments for your thesis, for a paper or for a real-world application? You want to leverage computational power to build automatically better algorithms? You want to improve the state of the art in solving a difficult computational problem? Then this course if for you.

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 of explaining and applying basic and advanced empirical methods for the design and analysis of algorithms (with an emphasis on high-performance heuristic algorithms that are inaccessible to analytical methods).
• To be capable of critically assessing empirical methods for the analysis and design of algorithms and their use as found in the research literature.

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
• automated algorithm configuration and parameter tuning
• automated algorithm selection
• self-tuning mechanisms

• Assignment 1 (released thu, 01/05; due mon, 01/09, 18:00 via e-mail)
• Assignment 2 (released thu, 01/12; due thu, 01/19, 18:00 via e-mail)

• 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.
• David 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. (PDF file from author's web page)
• Frank Hutter, Holger H. Hoos and Thomas Stützle: Automatic Algorithm Configuration based on Local Search. Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07), pp. 1152-1157, 2007. (get PDF file - 176k)
• Lin Xu, Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown: SATzilla: Portfolio-based Algorithm Selection for SAT. Journal of Artificial Intelligence Research, Volume 32, pp. 565–606, 2008. (abstract and electronic version - Open Access)
• Peter Sanders: Presenting data from experiments in algorithmics. Lecture Notes In Computer Science, Vol. 2547, Experimental Algorithmics, pp.181-196, 2002. (PDF file from CiteSeerX)
• Tim Hesterberg, David S. Moore, Shaun Monaghan, Ashley Clipson, Rachel Epstein: Bootstrap methods and permutation tests. Ch. 14 in David S. Moore, George P. McCabe: Introduction to the Practice of Statistics, 5th ed., W.H.Freeman, 2005. (PDF file from publisher's web site)

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

Lecture notes:

• Introduction:   [ get text file - 10KB ]
• Module 1:   [ get text file - 12KB ]

Slides (as used in class):

• Some introductory material (class 1):   [ get PDF version - 23KB ]