Algorithm Theory (DAT600)

The course gives insight into theory of algorithms and their performance. It includes a mathematical foundation for analysing the correctness of algorithms and for assessing their running time. The course introduces common computational problems and various techniques for solving them. The course also introduces the problem P=NP


Course description for study year 2025-2026. Please note that changes may occur.

See course description and exam/assesment information for this semester (2024-2025)
Facts

Course code

DAT600

Version

1

Credits (ECTS)

10

Semester tution start

Spring

Number of semesters

1

Exam semester

Spring

Language of instruction

English

Offered by
Time table

View course schedule

Content

The course revisits some mathematical notions such as growth of functions, standard notations for time complexity, some proof techniques, and other foundations from previous math classes. During the course we will visit problems such as sorting, traversal of trees, graphs and their applications, and matrix multiplication. We will develop solutions to these problems by applying algorithm design methods like divide and conquer, dynamic and greedy algorithms, and optimisation problems.

Learning outcome

After completing this course the student should be able to:

  • Be familiar with important principles for designing advanced algorithms and assessing their performance.
  • Be familiar with important problems and algorithms that solve them.
  • Can choose and apply different types of algorithms depending on what the information systems demand.
  • Be familiar with the classes of problems P, NP, NP-Hard, NP-Complete.
  • Can transform a problem to an optimisation problem and practically solve it using optimisation software packages.

Required prerequisite knowledge

None

Recommended prerequisites

DAT200 Algorithms and Datastructures

Exam

Form of assessment Weight Duration Marks Aid
Written exam 1/1 4 Hours Letter grades No printed or written materials are allowed. Approved basic calculator allowed

Digital exam.

Coursework requirements

Compulsory assignments

4 compulsory assignments.

Course teacher(s)

Course coordinator:

Nejm Saadallah

Head of Department:

Tom Ryen

Method of work

4 hours lectures and 2 hours exercises.

Overlapping courses

Course Reduction (SP)
Algorithm Theory (MID290_1) 10

Open for

Computer Science - Master of Science Degree Programme
Exchange programme at Faculty of Science and Technology

Admission requirements

Must meet the admission requirements of one of the study programmes the course is open for.

Course assessment

The faculty decides whether early dialogue should be conducted in all or selected groups of courses offered by the faculty. The purpose is to gather feedback from students for making changes and adjustments to the course during the current semester. In addition, a digital evaluation, students’ course evaluation, must be conducted at least once every three years. Its purpose is to collect students` experiences with the course.

Literature

Search for literature in Leganto