DM508: Algorithms and Complexity (5 ECTS)
STADS: 15000801Level
Bachelor course
Teaching period
The course is offered in the spring semester.
3rd quarter.
Teacher responsible
Email: joan@imada.sdu.dkTimetable
| Group | Type | Day | Time | Classroom | Weeks | Comment |
|---|---|---|---|---|---|---|
| Common | I | Tuesday | 10-12 | U46 | 05 | |
| Common | I | Tuesday | 10-12 | U26 | 06-09 | |
| Common | I | Tuesday | 10-11 | U26 | 10 | |
| Common | I | Thursday | 08-10 | U26 | 05-09 | |
| S1 | TE | Wednesday | 10-12 | U26 | 06-10 | |
| S1 | TE | Friday | 12-14 | U26 | 05-09 | |
| S1 | TE | Friday | 12-13 | U26 | 10 |
Show personal time table for this course.
Prerequisites:
None
Academic preconditions:
The content of DM507 Algorithms and Data Structures and DM504 Discrete structures must be known.
Course introduction
The purpose of the course is:
1. To give the students knowledge of methods for developing efficient algorithms.
2. 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
Subject overview
Randomized algorithms, lower bounds (information theoretic and adversary arguments), amortized analysis, Fibonacci heaps, string matching, NP-completeness.
Literature
- Meddeles ved kursets start.
Syllabus
See syllabus.
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 13-scale.
Obligatory assignments. Internal evaluation by teacher. Passed/not passed.
Expected working hours
The teaching method is based on three phase model.
Forelæsninger (21 timer) og eksaminatorier (21 timer).
Educational activities
Language
No recorded information about the language used in the course.
Course enrollment
See deadline of enrolment.
Tuition fees for single courses
See fees for single courses.
