Skip to main content
Breadcrumb

Algorithms

Course
DIT093
Master’s level
7,5 credits (ECTS)
Studietakt
50%
Undervisningstid
Day
Studieort
Göteborg
Undervisningsform
Campus
Undervisningsspråk
English
Duration
-
Application open
-
Anmälningskod
GU-18680
Tuition
Full education cost: 18 250 SEK
First payment: 18 250 SEK
Application opens 15 March 2021

About

The following topics are covered during the course:

- Introduction. What is an efficient algorithm?

- Tools for analysis of algorithms. O-notation. Analyzing loops and recursive calls.

- Solving recurrences;

- Data structures and algorithms. Review of basic data structures;

- Combining data structures. Merge-and-find;

- Graph algorithms;

- Greedy algorithms;

- Divide-and-conquer;

- Dynamic programming;

- Backtracking and Implicit search trees. Branch-and-bound;

- Short introduction to local search and approximation algorithms;

- Basic complexity theory. Complexity classes P, NP, and NPC, reductions. Examples of NP-complete problems. Coping with hard problems;

- Short introduction to other design techniques: local search, approximation algorithms, randomized algorithms, preprocessing, network flow.

Prerequisites and selection

Requirements

The requirement for the course is to have successfully completed coursers corresponding to 120 credits in the subject Computer Science or Mathematics including: 7.5 credits in discrete mathematics (DIT980 Discrete Mathematics for Computer Scientists, or the sub-course Introductory Algebra of MMG200 Mathematics I, or equivalent), additionally 15 credits in mathematics, 7.5 credits in imperative or object oriented programming (DIT012 Imperative Programming with Basic Object-orientation, or equivalent), additionally 7.5 credits in programming, 7.5 credits in data structures (DIT960 Data Structures, or equivalent). Applicants must prove knowledge of English: English 6/English B or the equivalent level of an internationally recognized test, for example TOEFL, IELTS.

Selection

Selection is based upon the number of credits from previous university studies, maximum 225 credits.

For admission to the summer 2021 and onward the following selection applies: selection is based upon the number of credits from previous university studies, maximum 165 credits.