NDAK14006U Algorithm Engineering
Algorithm engineering is a discipline between algorithm theory
and computing practice. Theoretical algorithmics supplies us with a
rich set of algorithms and data structures that, in principle,
enable us to solve complex and hard real-world problems. Often the
algorithms are
designed having the classical random-access machine in mind and the
resource requirements of the developed algorithms are analysed in
the worst-case or average-case scenario.
In algorithm engineering we design and analyse algorithms for more
realistic machine models that take into account the existence of
branch predictors, caches, disks, multi-cores, and clusters. In our
analysis we take into account the constant factors in the leading
terms of the resource bounds. We treat programs as first-class
citizens and investigate how algorithms can be turned into reliable
and efficient implementations and how these programs can be
packaged into easy-to-use software libraries. We do experiments
with real-world data and investigate how to solve typical problem
instances efficiently.
To summarize, algorithm engineering can be seen as a general
methodology for algorithmics. Its heart is an interwoven cycle of
design, analysis, implementation, and experimentation. We will
design algorithms and prove theorems about them, we will implement
our algorithms and do experiments with the implementations. We will
learn best practices of experimentation and library design.
Table of contents
- Introduction
- Modelling real applications
- Realistic models of computation
- Algorithm design hierarchy
- Meticulous analysis
- Implementation aspects
- Experimentation
- Library design
- Case studies
Knowledge
In the course the student will learn
- key concepts found in the literature on algorithm engineering
- best practices in algorithm engineering
- different models of computation used to predict program
performance
- tools used in a meticulous analysis of programs
- how to use of scientific method in the area of empirical
algorithmics
- architectural details of a modern program library on algorithms
and data structures.
Skills
After the course the student should be able to
- model computational problems that appear in real-world
applications
- design algorithms and data structures for different models of
computation
- describe algorithms using pseudo-code
- analyse the key performance characteristics of algorithms and
data structures
- implement algorithms efficiently using a concrete programming
language
- carry out computational experiments that yield correct, general,
informative, and useful results.
Competences
The student will get a deep understanding of how to
- fill in the gap between algorithm theory and computing practice
- transform theoretical designs into efficient
programs.
Catherine C. McGeorg, A Guide to Experimental
Algorithmics, Cambridge (2012)
Matthias Müller-Hannemann and Stefan Schirra (Eds.), Algorithm
Engineering: Bridging the Gap between Algorithm Theory and
Practice, Springer (2010)
- B.Sc.-level course on programming
- This course (AE) replaces the course Data Structures: Theory and Practice (DS:TP) in our M.Sc. programme so a student who has previously passed DS:TP cannot take AE.
- Additionally, AE replaces DS:TP in the specialization profile Algorithms and Data Structures
- seminar presentations
- assignments
- project
- project workshop
- written test
- Category
- Hours
- Colloquia
- 10
- Exam
- 21
- Exercises
- 60
- Lectures
- 35
- Project work
- 60
- Seminar
- 20
- Total
- 206
As
an exchange, guest and credit student - click here!
Continuing Education - click here!
- Credit
- 7,5 ECTS
- Type of assessment
- Continuous assessment, 9 weeksThe exam consists of 4 elements:
- Written test (4 hours) in the second examination week
- Active participation and presentation
- 4 assignments
- 3-weeks project that results in a project workshop (4 hours) in the first examination week
In the final grade the weight of the different criteria is as follows: Assignments 25%, participation and presentations 20%, project 25%, and final 4-hours written test 30%. - Aid
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners
- Re-exam
- Grading is based on the same evaluation criteria as the ordinary exam; selected course elements can be reused or remade completely.
Criteria for exam assesment
See Learning Outcome
Course information
- Language
- English
- Course code
- NDAK14006U
- Credit
- 7,5 ECTS
- Level
- Full Degree Master
- Duration
- 1 block
- Placement
- Block 1
- Schedule
- C (Mon 13-17 + Wednes 8-17)
- Course capacity
- No limit
- Continuing and further education
- Study board
- Study Board of Mathematics and Computer Science
Contracting department
- Department of Computer Science
Course responsibles
- Jyrki Katajainen (5-6f7e77706e45696e33707a336970)