DM508: Algorithms and Complexity (5 ECTS)

STADS: 15016801

Level
Bachelor course

Teaching period
The course is offered in the spring semester.

Teacher responsible
Email: joan@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. Fælles med DM553 Kompleksitet og beregnelighed.

Prerequisites:
None

Academic preconditions:
The content of DM507 Algorithms and Data Structures and DM538 Algorithms and Probability OR DM528 Combinatorics, Probability, and Randomized Algorithms is assumed known.

Course introduction
The purpose of the course is:

• To give the students knowledge of methods for developing and analysing efficient algorithms.
• To give the students knowledge of the complexity of algorithms and certain aspects of complexity theory.

Qualifications
The students will gain insight into techniques for designing efficient algorithms and into the theory concerning the complexity of problems and algorithms for them. After the course the students will be able to use this knowledge in relevant situations to:

• prove lower bounds on the complexity of problems using information theoretic arguments.
• prove lower bounds on the complexity of problems and algorithms using adversary arguments.
• formally define the classes P and NP, explain Cook's Theorem and prove that various problems are NP-Complete.
• explain and analyze approximation algorithms.

Expected learning outcome
After the course the students should be able to:

• prove lower bounds on the complexity of problems using information theoretic arguments
•  prove lower bounds on the complexity of problems and algorithms using adversary arguments
• modify known algorithms and data structures to special cases of known problems and to new problems
• design and analyze new approximation algorithms to solve problems which resemble problems from the course
• formally define the classes P and NP
• explain Cook's Theorem, which shows that SAT is NP-Complete
• prove that various problems are NP-Complete

Subject overview
Lower bounds (information theoretic and adversary arguments), NP-completeness, approximation algorithms.

Literature

Meddeles ved kursets start.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
Obligatory assignments. Internal evaluation by teacher. Passed/not passed. Internal evaluation by teacher (15016812)

Assessment and marking:
Oral exam. External marking. Marks according to the Danish 7-scale. (15016802)

Expected working hours
The teaching method is based on three phase model.
Intro phase: 18 hours
Skills training phase: 18 hours, hereof:
 - Tutorials: 18 hours

Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.