CPSC 536H - Empirical Algorithmics (Spring 2012)

[General Info] · [Course Outline] · [Paper reviews] · [Course Projects] · [Assignments] · [Grading] · [Resources]
Latest news (12/04/05):

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

   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:

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.


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

Paper reviews

Paper reviews are conducted by each student individually. 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/21, tue, 18:00 PST     paper proposals due (via e-mail, in PDF format)
    02/24, fri, 18:00 PST     feedback on proposal + selection of paper
    03/05, mon, 18:00 PST     paper reviews due (vie e-mail, in PDF format)


Course projects

Course projects are conducted by each student individually. 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):

    03/09, fri, 18:00 PST     project proposals due (vie e-mail, in PDF format)
    03/23, fri, 18:00 PDT     project status updates due (vie e-mail, in PDF format)
    04/20, fri, 18:00 PDT     final project reports due (vie e-mail, in PDF format)
    last week of April     project presentations (details TBA)


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

Lecture notes:

Slides (as used in class):

Other materials: (will be posted throughout the course)

last update: 12/04/05 [hh]