NDAK14006U Algorithm Engineering
Volume
2014/2015  Language  English   Credit  7,5 ECTS   Level  Full Degree Master   Duration  1 block   Placement  Block 1  Schedule  C (Mon 1317 + Wednes 817)   Course capacity  No limit  Continuing and further
education   Study board  Study Board of Mathematics and Computer
Science   Contracting department   Department of Computer Science
  Course responsible   Jyrki Katajainen (5707f78716f466a6f34717b346a71)
  Saved on the
03122014 
Education  MSc Programme in Computer
Science 
Content  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 realworld problems. Often the
algorithms are
designed having the classical randomaccess machine in mind and the
resource requirements of the developed algorithms are analysed in
the worstcase or averagecase 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, multicores, and clusters. In our
analysis we take into account the constant factors in the leading
terms of the resource bounds. We treat programs as firstclass
citizens and investigate how algorithms can be turned into reliable
and efficient implementations and how these programs can be
packaged into easytouse software libraries. We do experiments
with realworld 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  Learning Outcome  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 realworld
applications
 design algorithms and data structures for different models of
computation
 describe algorithms using pseudocode
 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.  Literature  Catherine C. McGeorg, A Guide to Experimental
Algorithmics, Cambridge (2012)
Matthias MüllerHannemann and Stefan Schirra (Eds.), Algorithm
Engineering: Bridging the Gap between Algorithm Theory and
Practice, Springer (2010)  Teaching and learning methods   lectures
 seminar presentations
 assignments
 project
 project workshop
 written test 
Formal requirements   B.Sc.level course on algorithms and data
structures
 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 
Academic qualifications  The course requires a solid foundation in
algorithmics. Since there will be handson programming exercises,
experience in one or more imperative programming languages
(preferably C++) is necessary. 
Sign up  Self Service at KUnet

Exam  Credit  7,5 ECTS   Type of assessment  Continuous assessment, 9 weeks The exam consists of 4 elements:
 Written test (4 hours) in the second examination week
 Active participation and presentation
 4 assignments
 3weeks 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 4hours written test 30%.   Aid  All aids allowed   Marking scale  7point grading scale   Censorship form  No external censorship
Several internal examiners   Reexam  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 

Workload  Category  Hours  Lectures  35  Seminar  20  Exercises  60  Project work  60  Colloquia  10  Exam  21  Total  206 

Saved on the
03122014

