2017 Spring 2016 Spring
Show the courses of study containg this course Se overgangsordninger
Dansk English

DM849: Analysis Driven Engineering of Algorithms (5 ECTS)

STADS: 15018301

Level
Master's level course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: nebel@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Comment:
AFLYST F17!

Prerequisites:
Bachelor degree in computer science, physics, mathematics, applied mathematics, mathematics-economy or comparable.

Academic preconditions:
Students taking the course are expected to:
  • be able design and implement programs, using standard algorithmic approaches and data structures
  • be able to judge the complexity of algorithms, with regard to runtime as well as with regard to space usage.
 


Course introduction
The goal of this course is to introduce students to the ideas of algorithm engineering based on average-case results for the algorithm’s efficiency. Furthermore, fundamental tools and techniques for performing an average-case analysis are taught. The probability models underlying such an analysis can be derived from representative input data for the application in mind. The course will cover fundamental approaches to derive such a model based on ideas from machine learning and statistics.

The course builds on the knowledge acquired in the courses DM551 Algorithms and Probability. The course aims at applying the covered techniques to problems arising in Computer Science or other disciplines including Biology and Chemistry.

In relation to the competence profile of the degree it is the explicit focus of the course to:

  • Provide knowledge on a range of specialized models and methods developed in computer science based on the highest international research standards, including topics from the subject's research front
  • Give knowledge of computer science models and methods for use in other professional areas
  • Describe, analyze, and solve advanced computer scientific problems using the models they learned.
  • Shed light on stated hypotheses with a qualified theoretical basis and be critical of both own and others research results and scientific models.
  • Develop new variants of the learned methods, where the concrete problem requires it.
  • Disseminate research-based knowledge and discuss professional and scientific problems with both colleagues and non-specialists.
  • Plan and execute scientific projects of high standard, including managing work situations that are complex, unpredictable, and require novel solutions.
  • Take responsibility of own professional development and specialization have learned.
 


Expected learning outcome
The learning objectives of the course is that the student demonstrates the ability to:
  • be able to analyze the average-case performance of simple algorithms and data structures
  • understand how to use corresponding results in order to improve an algorithm
  • understand and implement new methods for the tool-based analysis of algorithms
  • be able to apply those methods to algorithms and data structures
 


Subject overview
The following main topics are contained in the course:
Algorithm engineering cycle, combinatorial cost measures, generating functions, symbolic method to analyze data structures, asymptotic methods for coefficient extraction, stochastic grammars, maximum likelihood training, Earley parsing
 


Literature
    Meddeles ved kursets start.


Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
  1. Project assignment. (5 ECTS). Internal assessment by teacher, pass/fail. No aids allowed. (15018302).
Expected working hours
The teaching method is based on three phase model.
Intro phase: 18 hours
Skills training phase: 24 hours, hereof:
 - Tutorials: 9 hours
 - Laboratory exercises: 15 hours

Educational activities
Using the acquired knowledge in projects.Educational form
 In the intro phase, concepts, theories and models are introduced and put into perspective. In the training phase, students train their skills through exercises and dig deeper into the subject matter. 
 
 


Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.