| TDDD20 |
Design and Analysis of Algorithms, 6 ECTS credits.
/Konstruktion och analys av algoritmer/
For:
D
DAV
I
Ii
IT
MMAT
|
| |
Prel. scheduled
hours: 30
Rec. self-study hours: 130
|
| |
Area of Education: Technology
Main field of studies: Computer Science, Computer Engineering, Information Technology
|
| |
Advancement level
(G1, G2, A): A
|
|
Aim:
The primary aim of this course is to increase the student's skills in constructing and analysing algorithms. After the course, the students should be able to
- construct algorithms for computational problems
- prove the correctness of algorithms
- analyze and evaluate algorithms for computational problems
|
|
Prerequisites: (valid for students admitted to programmes within which the course is offered)
Discrete mathematics and logic. An introductory course on data structures and algorithms. That is, the student is expected to be familiar with asymptotic notation, basic data structures, such as lists, stacks, queues, trees etc., and algorithms for fundamental problems, such as searching, sorting, etc. Basic knowledge in probability theory and optimization.
Note: Admission requirements for non-programme students usually also include admission requirements for the programme and threshhold requirements for progression within the programme, or corresponding.
|
|
Supplementary courses:
Algorithmic problem solving
|
|
Organisation:
The theory is presented during the lectures and examples of algorithm construction/analysis are presented. Furthermore, the students are given the opportunity to construct and analyze different algorithms.
|
|
Course contents:
The course contains three main parts:
- Part 1: Basic techniques. Greedy algorithms, decomposition, and dynamic programming.
- Part 2: NP-completeness. The theory of NP-completeness and its consequences.
- Part 3: Inexact methods. Construction and analysis of approximation algorithms and randomized algorithms.
|
|
Course literature:
Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein C.: Introduction to Algorithms: Second or Third Edition. The MIT Press.
|
|
Examination: |
|
Written examination
|
6 ECTS
|
| |
|
|
Course language is Swedish.
Department offering the course: IDA.
Director of Studies: Ahmed Rezine
Examiner: Peter Jonsson
Course Syllabus in Swedish
|