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.