Empirical Algorithmics (Spring 2006)

Preliminary course outline (subject to adjustments)

Module 1: Introduction

• The role of empirical methods in computer science
• The scientific method
• Exploratory vs. confirmatory analysis
• Empirical algorithmics: Goals and Issues
• Course overview

Module 2: Deterministic algorithms for decision problems

• Introduction to decision problems
• Empirical analysis of a single algorithm
• Empirical analysis of multiple algorithms
• Impact of parameter settings on performance
• Benchmark selection
• Measuring run-time
• Statistical hypothesis testing

Module 3: Randomised algorithms for decision problems

Module 4: Algorithms with error for decision problems

Module 5: Algorithms for optimisation problems

Module 6: Advanced topics