Kursussøgning, efter- og videreuddannelse – Københavns Universitet

Videresend til en ven Resize Print Bookmark and Share

Kursussøgning, efter- og videreuddannelse

Algorithm Engineering (AE)

Practical information
Study year 2016/2017
Time
Block 1
Programme level Full Degree Master
ECTS 7,5 ECTS
Course responsible
  • Jyrki Katajainen (5-7180797270476b7035727c356b72)
  • Department of Computer Science
Course number: NDAK16000U

Course 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 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, and 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 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.

Recommended prerequisites

The course requires a solid foundation in algorithmics. Since there will be hands-on programming exercises, experience in one or more imperative programming languages (preferably C++) is necessary.

Sign up


As an exchange, guest and credit student - click here!

Continuing Education - click here!

Education

MSc Programme in Computer Science

Studyboard

Study Board of Mathematics and Computer Science

Course type

Single subject courses (day)

Duration

1 block

Schedulegroup

C
---- SKEMA LINK ----

Teaching and learning methods

- lectures
- seminar presentations
- assignments
- project
- project workshop
- written test

Capacity

No limit

Language

English

Literature

Expected to be:

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)

Workload

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

Exam

Type of assessment

Continuous assessment
The exam consists of four elements:
- seminar presentation
- 4 assignments
- 3-weeks project to be presented at a workshop in the first examination week
- written test (4 hours) in the second examination week

In the final grade the weight of the different criteria is as follows: assignments 25%, seminar presentation 20%, project (including presentation) 25%, and final 4-hours written test 30%.

Aid

All aids allowed

Marking scale

7-point grading scale

Criteria for exam assessment

See Learning Outcome

Censorship form

No external censorship
Several internal examiners

Re-exam

Resubmission of (possibly revised) course elements; elements not redone are carried over with their original assessments. Assignments and/or project reports must be resubmitted no later than two weeks before the re-exam date; seminar and/or project presentations must be held no later than one week before the re-exam date; a new written test (if requested) will be administered on the re-exam date itself.

Mere information om kurset
Er du BA- eller KA-studerende?
Er du bachelor- eller kandidat-studerende, så find dette kursus i kursusbasen for studerende:

Kursusinformation for indskrevne studerende