Complexity Theory
Course offered :
- Current semester
- Next semester
Current programmes of study
Course offered by
| Number of credits | 10 |
| Course offered (semester) | Spring |
| Subject overlap | I235: 10 ECTS |
| Schedule | Schedule |
| Reading list | Reading list |
Language of Instruction
English
Pre-requirements
At least 60 ECTS in computer science, preferably including some mathematics
Learning Outcomes
At the completion of INF235 the student should:
- have a deeper understanding of what an algorithm is and of which problems that theoretically can be solved by an algorithm.
- understand the relationship between formal languages and Turing machines.
- know how to classify problems into complexity classes for time and memory usage.
- be able to decide which problems can be feasibly solved, either using an exact or an approximate method.
Contact Information
studieveileder@ii.uib.no
Course offered (semester)
Spring
Language of Instruction
English
Aim and Content
Complexity is a target on available resources (time and space) that is demanded to solve a problem algorithmically. The course gives a precise formal definition of the algorithm concept (via Turing machines). The main emphasis is on important complexity classes with emphasis on NP-complete problems. Approximations algorithms for NP-hard problems.
Learning Outcomes
At the completion of INF235 the student should:
- have a deeper understanding of what an algorithm is and of which problems that theoretically can be solved by an algorithm.
- understand the relationship between formal languages and Turing machines.
- know how to classify problems into complexity classes for time and memory usage.
- be able to decide which problems can be feasibly solved, either using an exact or an approximate method.
Pre-requirements
At least 60 ECTS in computer science, preferably including some mathematics
Recommended previous knowledge
Subject Overlap
I235: 10 ECTS
Compulsory Requirements
Exercises.
Compulsory assignments are valid two semesters, the semester of the approval and the following semester.
Assessment methods
Written exam. It is opportunity for grades on exercises, which can be included in the final grade. If less than 20 students are taking the course, it can be oral exam.
No aids allowed.
Grading Scale
The grading scale used is A to F. Grade A is the highest passing grade in the grading scale, grade F is a fail.
Contact Information
studieveileder@ii.uib.no