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
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
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 SaadallahHead of Department:
Tom RyenMethod of work
4 hours lectures and 2 hours exercises.
Overlapping courses
| Course | Reduction (SP) |
|---|---|
| Algorithm Theory (MID290_1) | 10 |
Open for
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.
