Design of Efficient Algorithms
Introduction
This module deals with efficient algorithms, optimisation, and approximation algorithms.
Contents
Architecture and implementation of formal systems for the design of efficient algorithms, correctness-preserving optimisation, programme verification and synthesis. Design and analysis of approximation algorithms.
Learning Objectives
Students will be familiar with and understand basic techniques of formal programme development and its implementation. Students will be able to anticipate efficiency problems when designing algorithms and respond accordingly. Students will write better programmes that are highly optimised in their runtime-critical areas. Students will be able to analyse simple approximation methods in terms of their quality. They understand basic design techniques such as greedy, local search, scaling and methods based on linear programming and can also apply these to new problems.
Examination Methods
- Either a 90-minute written exam.
- Or a 30 minute oral examination.
Lecture: Efficient Algorithms
SWS: 2 ECTS: 2
Exercise: Efficient Algorithms Exercise
SWS: 2 ECTS: 4
Module Competences
| ID | Description | Disciplines | Prerequisites | Evidence | Author | Source |
|---|---|---|---|---|---|---|
| eff_algorithms_1 | describe formal systems for the development of efficient algorithms and correctness-preserving optimisation | Computer Science | exemplary application of those formal methods | University of Potsdam | Link |