CPSC 536H - Empirical Algorithmics (Spring 2010)

[General Info] · [Course Outline] · [Paper reviews] · [Course Projects] · [Assignments] · [Grading] · [Resources]
Latest news (10/03/25):

   Tue+Thu, 11:00-13:30 in
ICCS 238
   First class: Thu, 2010/01/07

   Holger H. Hoos
   E-mail: hoos "at" cs.ubc.ca
   Office: ICICS/CS complex, Room X541
   Office hour: Tue, 14:00-15:00 or by appointment

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

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:

Prerequisite knowledge: Algorithms, basic knowledge of statistics, high proficiency in programming

Topics covered in this course include:

Preliminary course outline

Note: The course will consist of three components: (1) regular classes, (2) paper presentations (by participants) and discussions, and (3) a sizeable course project. There will also be homework assignments. 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.


Course projects

Course projects are conducted individually. They involve practical work in empirical algorithmics that clearly demonstrates proficiency with the methods and concepts covered in the course. All projects should have an analysis component. Ideally, projects also should have a design component (e.g., automated algorithm configuration).

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/09, tue, 23:59:59 PST     project proposals due (vie e-mail, in PDF format)
    03/09, tue, 23:59:59 PST     project status updates due (vie e-mail, in PDF format)
    04/09, fri, 23:59:59 PST     final project reports due (vie e-mail, in PDF format)
    mid-April     project presentations (details TBA)


Final grades for this course will be determined based on the following four components: (1) A sizable course project (ca. 45%); (2) a paper review (ca. 25%); (3) homework assignments (ca. 20%) and (4) in-class participation (ca. 10%). 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).


Primary literature
Supplementary literature (This list will be extended throughout the term.)

Lecture notes: (will be posted / updated before each class)

Slides (as used in class): (will be posted before each class)

Other materials: (will be posted throughout the course)

last update: 10/03/25 [hh]