DM508: Algorithms and Complexity (5 ECTS)

STADS: 15005801

Level
Bachelor course

Teaching period
The course is offered in the spring semester.
4th quarter.

Teacher responsible
Email: joan@imada.sdu.dk

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

Prerequisites:
None

Academic preconditions:
The content of DM507 Algorithms and Data Structures and DM538 Algorithms and Probability.

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:
- design and analyze randomized algorithms.
- 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.
- use amortized analysis on relevant algorithms.
- explain Fibonacci heaps.
- explain algorithms for string matching.
- formally define the classes P and NP, explain Cook's Theorem and prove that various problems are NP-Complete.

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
• use amortized analysis on relevant algorithms
• explain Fibonacci heaps and prove their running time
• explain algorithms for string matching and prove their running time
• modify known algorithms and data structures to special cases of known problems and to new problems
• design and analyze new 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), amortized analysis, Fibonacci heaps, string matching, NP-completeness.

Literature

Meddeles ved kursets start

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral exam. External marking. Marks according to the Danish 7-scale.
Obligatory assignments. Internal evaluation by teacher. Passed/not passed.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger (18 timer) og eksaminatorier (18 timer).
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.