TTIT33 Algorithms and Optimization, 9,8 ECTS-points
/Tema 3: Algoritmer och Optimering/

Advancement level:
B

Aim:
Skills in mathematically modeling combinatorical optimization problems and find the complexity of these problems using complexity theory. Knowledge of well-known optimization problems and algorithms to solve them. Understanding of and skills in methods for design and analysis of algorithms. Knowledge of basic abstract data types and efficient implementations of these abstract data types.

Prerequisites:
Basic mathematics (e.g. mathematics in semester 1), TTIT 31 Programming

Supplementary courses:
TDDA 32 Design and Analysis of Algorithms, TAOP 19 Combinatorical Optimization, Advanced Course

Course organization:
See studiehandboken, part 1. Some parts are integrated with TTIT 36 Communication IT.

Course content:
Basic linear programming, problem classification, network problems (algorithms based on graph search), minimal spanning tree, tree search, non-optimizing algorithms (approximating algorithms and heuristics). Time complexity of algorithms, abstract data types (list, stack, queue, mapping, tree, set, dictionary, priority queue, graph) and their implementations, sorting and selection, methods for algorithm design (divide and conquer, dynamic programming, greedy algorithms).

Course literature:
See literature list.

TEN1Written examination, 4 p.
LAB1Labratory work, 2,5 p.
MOM1, 0 p.
MOM2, 0 p.
Course language is swedish.