# 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

- CSCI 3110: Design and Analysis of Algorithms

## Related Courses

*CSCI 4113: Algorithms II*explores advanced algorithms from a mostly theoretical point of view.*CSCI 4117/6057: Advanced Data Structures*explores advanced data structure from a mostly theoretical point of view.

# Course Organization

Component | Dates |
---|---|

Introduction | Weeks 1–2: Jan 8–19 |

Student presentations | Weeks 3–8: Jan 22–Mar 12 |

Optional material | Week 9: Mar 14–19 |

Project presentations | Weeks 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 & 29 | Norbert Zeh |

Algorithm design: Time-space trade-offs | 3.4 | Jan 31 | Norbert Zeh |

Algorithm analysis: Worst-case, average-case & amortized analysis; realistic input models | 4.2, 4.3 & 4.5 | Feb 2 | Norbert Zeh |

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 | Norbert Zeh |

Computer models: Memory hierarchies, success stories | 5.2 & 5.5 | Feb 9 | Norbert Zeh |

Computer models: Parallel computing | 5.3, 5.4 & 5.6 | Feb 12 | Vishwas Bordekar |

Implementation: Correctness & efficiency | 6.2 & 6.3 | Feb 14 | Jackie Purdue |

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

- One 50-minute presentation on a topic in the above table
- Course project

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