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.
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
Course assessment
There must be an early dialogue between the course supervisor, the student union representative and the students. The purpose is feedback from the students for changes and adjustments in the course for the current semester.In addition, a digital course evaluation must be carried out at least every three years. Its purpose is to gather the students experiences with the course.