Overview

Course Description

This course gives an introduction to Algorithm Engineering, which focuses on developing efficient algorithms and easy-to-use, well-tested, and high-performance implementations of these algorithms for use in the real world.

Specific aspects of algorithm engineering that will be discussed are:

Modelling: How to turn a real-world problem into a well-posed algorithmic problem so it is possible to design an algorithm for it and evaluate its correctness and efficiency. We will also discuss how decisions made during modelling will affect the design of the algorithm.

Algorithm design: We will discuss the iterative process that leads us from the model developed in the modelling phase to an algorithm and a plan for its implementation. In contrast to Algorithm Theory, the focus on implementation is an integral part of the design process. Key concerns are that the developed algorithms be simple, flexible, scalable, and robust.

Analysis: We will discuss how analysis is, just as in Algorithm Theory, a key tool to guide our design decisions. However, differently than in Algorithm Theory, our focus is on understanding the behaviour of the algorithm on realistic inputs, not on the worst or average case.

Computer models: Theory focuses on simple models of computations to allow the study of fundamental complexity-theoretic questions. These models do not reflect the reality of modern computer systems, which are often parallel computers and have hierarchical memory systems. To model the behaviour of algorithms on real computers, realistic models need to be used as a basis of the analysis of algorithms.

Implementation: Theoreticians consider the translation of a pencil-and-paper algorithm into actual code to be a mere formality that should be carried out by the application programmer. However, the choices made in implementing an algorithm can have a tremendous impact on its performance and robustness, and often requires substantial algorithmic expertise.

Algorithm libraries: Algorithm libraries are a key tool for sharing the results of algorithm engineering work with practitioners and other algorithm engineers. Developing such libraries poses very different (and greater) challenges than developing good algorithms for specific applications because the scenarios in which these libraries may be applied are more varied than for a specific algorithm and are often even difficult to anticipate. Thus, it is important to strike a careful balance between generality and tuning for performance on certain types of inputs. Flexibility and modularity is of extreme importance to ensure the algorithms offered by the library can be customized for specific applications as much as possible.

Experimentation: Experimentation is probably the greatest departure of Algorithm Engineering from classical Algorithm Theory. Inspired by the Scientific Method, Algorithm Engineering uses falsifiable hypotheses about the behaviour of the algorithm and the structure of the data encountered in specific applications to drive the algorithm development process. Carefully designed experiments are the key to confirming or refuting these hypotheses and thereby gain insight into the problem and the algorithm's behaviour.

Students will explore these aspects of Algorithm Engineering through introductory lectures given by the course instructor, reading assignments and lectures given by students, and a project that forces them to apply the Algorithm Engineering methodology in a limited scope.

Prerequisites

Related Courses

Course Organization

ComponentDates
IntroductionWeeks 1–2: Jan 8–19
Student presentationsWeeks 3–8: Jan 22–Mar 12
Optional materialWeek 9: Mar 14–19
Project presentationsWeeks 10–12: Mar 21–Apr 9

Lecture Topics

Topic Sections in Book Date Presenter
Modelling fundamentals & graph-based models 2.2 & 2.3.1 Jan 22 Yaser Alkayale
Modelling: Mixed integer programming, convex programming, constraint programming & algebraic modelling languages 2.3.2–2.3.5 Jan 24 Jacklyn Purdue
Algorithm design: Simplicity & scalability 3.2 & 3.3 Jan 26 Oyshee Saha Roy
Algorithm design: Time-space trade-offs 3.4 Jan 29 TBD
Algorithm design: Robustness 3.5 Jan 31 Abhi Patel
Algorithm analysis: Worst-case, average-case & amortized analysis; realistic input models 4.2, 4.3 & 4.5 Feb 2 Zongming Liu
Algorithm analysis: Smoothed analysis 4.4 Feb 5 Mat Kallada
Algorithm analysis: Computational testing, representative operation counts & experimental study of asymptotic performance 4.6–4.8 Feb 7 TBD
Computer models: Memory hierarchies, success stories 5.2 & 5.5 Feb 9 TBD
Computer models: Parallel computing 5.3, 5.4 & 5.6 Feb 12 Vishwas Bordekar
Implementation: Correctness & efficiency 6.2 & 6.3 Feb 14 TBD
Implementation: Flexibility & ease of use; efficiency of implementation; geometric algorithms 6.4–6.7 Feb 16 TBD
Algorithm libraries: Overview, building blocks & design goals; fundamental operations 7.2–7.5 Feb 26 TBD
Algorithm libraries: Advanced number types, basic data structures, graphs & computational geometry 7.6–7.9 Feb 28 TBD
Experiments: Planning, set-up & running experiments 8.2 & 8.5 Mar 2 Damien Robichaud
Experiments: Test data generation & test data libraries 8.3 & 8.4 Mar 5 TBD
Experiments: Evaluating & reporting experimental results 8.6 & 8.7 Mar 7 TBD
Case studies: Shortest paths & Steiner tree 9.2 & 9.3 Mar 9 TBD
Case studies: Voronoi diagrams 9.4 Mar 12 TBD

Main Reference

Matthias Müller-Hannemann and Stefan Schirra. Algorithm Engineering: Bridging the Gap Between Algorithm Theory and Practice. Springer-Verlag, 2010.

Evaluation

Grade = 50% * Presentation + 50% * Project

(Details on specific expectations, as discussed in the first class, will be posted here soon.)

Policies

Late Assignments

Late assignments are accepted only if you were sick on the day the assignment was due or if there is an important event in your personal life that prevents you from completing the assignment on time. In the latter case, you must discuss these circumstances with me in advance to apply for a reasonable extension.

Plagiarism

I will not tolerate any form of plagiarism (copying from your classmates, copying solutions from the web, etc.). According to university regulations, I have to report you to the Faculty's Integrity Officer if I suspect you of academic dishonesty, and I will. The Integrity Officer may refer your case to the Senate Committee on Plagiarism. The penalty for plagiarism can range from failing the course to expulsion from the university. So please save me and yourself the aggravation. For more information, make sure you read the Dalhousie Academic Integrity Page.