Breadcrumb

Algorithms

Course
DIT093
Master’s level
7.5 credits (ECTS)
Study pace
50%
Time
Day
Location
Göteborg
Study form
Campus
Language
English
Duration
-
Application period
-
Application code
GU-86000
Tuition
Full education cost: 19 253 SEK
First payment: 19 253 SEK

No fees are charged for EU and EEA citizens, Swedish residence permit holders and exchange students.

More information about tuition fees

About

The course topics are as follows:

  • 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

Entry requirements

The requirement for the course is to have successfully completed coursers corresponding to 120 hp 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, orequivalent),
- additionally 10 creditsin mathematics,
- 7\.5 creditsin imperative or object oriented programming (DIT012 ImperativeProgramming with Basic Object-orientation, or equivalent),
- additionally 7.5 creditsin programming,
- 7\.5 creditsin data structures (DIT960 Data Structures, DIT375 Python for DataScientists or equivalent).

Applicants must prove knowledge of English: English 6/English B or the equivalent levelof an internationally recognized test, for example TOEFL, IELTS

Selection

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