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
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 will be held in all courses or in selected groups of courses. The aim is to collect student feedback for improvements during the semester. In addition, a digital course evaluation must be conducted at least every three years to gather students’ experiences.