DM508: Algorithms and Complexity (5 ECTS)
STADS: 15005801
Level
Bachelor course
Teaching period
The course is offered in the spring semester.
3rd quarter.
Teacher responsible
Email: joan@imada.sdu.dk
Timetable
Group |
Type |
Day |
Time |
Classroom |
Weeks |
Comment |
Common |
I |
Monday |
08-10 |
U26 |
05-10 |
|
Common |
I |
Monday |
08-10 |
U26 |
05-10 |
|
Common |
I |
Monday |
08-10 |
U26 |
05-10 |
|
Common |
I |
Monday |
08-10 |
U26 |
05-10 |
|
Common |
I |
Monday |
08-10 |
U26 |
05-10 |
|
Common |
I |
Monday |
08-10 |
U26 |
05-10 |
|
Common |
I |
Monday |
08-10 |
U26 |
05-10 |
|
Common |
I |
Monday |
08-10 |
U26 |
05-10 |
|
Common |
I |
Wednesday |
10-12 |
U26 |
05 |
|
Common |
I |
Wednesday |
10-12 |
U26 |
05 |
|
Common |
I |
Wednesday |
10-12 |
U26 |
05 |
|
Common |
I |
Wednesday |
10-12 |
U26 |
05 |
|
Common |
I |
Wednesday |
10-12 |
U26 |
05 |
|
Common |
I |
Wednesday |
10-12 |
U26 |
05 |
|
Common |
I |
Wednesday |
10-12 |
U26 |
05 |
|
Common |
I |
Wednesday |
10-12 |
U26 |
05 |
|
Common |
I |
Friday |
10-12 |
U26 |
06 |
|
Common |
I |
Friday |
10-12 |
U26 |
06 |
|
Common |
I |
Friday |
10-12 |
U26 |
06, 08, 10 |
|
Common |
I |
Friday |
10-12 |
U26 |
06 |
|
Common |
I |
Friday |
10-12 |
U26 |
06 |
|
Common |
I |
Friday |
10-12 |
U26 |
06 |
|
Common |
I |
Friday |
10-12 |
U26 |
06 |
|
Common |
I |
Friday |
10-12 |
U26 |
06 |
|
Common |
I |
Friday |
10-12 |
U26 |
08 |
|
Common |
I |
Friday |
10-12 |
U26 |
08 |
|
Common |
I |
Friday |
10-12 |
U26 |
08 |
|
Common |
I |
Friday |
10-12 |
U26 |
08 |
|
Common |
I |
Friday |
10-12 |
U26 |
08 |
|
Common |
I |
Friday |
10-12 |
U26 |
08 |
|
Common |
I |
Friday |
10-12 |
U26 |
08 |
|
Common |
I |
Friday |
10-12 |
U26 |
10 |
|
Common |
I |
Friday |
10-12 |
U26 |
10 |
|
Common |
I |
Friday |
10-12 |
U26 |
10 |
|
Common |
I |
Friday |
10-12 |
U26 |
10 |
|
Common |
I |
Friday |
10-12 |
U26 |
10 |
|
Common |
I |
Friday |
10-12 |
U26 |
10 |
|
Common |
I |
Friday |
10-12 |
U26 |
10 |
|
S1 |
TE |
Wednesday |
10-12 |
U26 |
06-11 |
|
S1 |
TE |
Wednesday |
10-12 |
U26 |
06-08,10-11 |
|
S1 |
TE |
Wednesday |
10-12 |
U26 |
06-11 |
|
S1 |
TE |
Wednesday |
10-12 |
U26 |
06-11 |
|
S1 |
TE |
Wednesday |
10-12 |
U26 |
06-11 |
|
S1 |
TE |
Wednesday |
10-12 |
U26 |
06-11 |
|
S1 |
TE |
Wednesday |
10-12 |
U26 |
06-11 |
|
S1 |
TE |
Wednesday |
10-12 |
U26 |
06-11 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
05 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
05 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
05 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
05 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
05, 07, 09, 11 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
05 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
05 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
05 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
07 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
07 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
07 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
07 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
07 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
07 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
07 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
09 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
09 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
09 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
09 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
09 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
09 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
09 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
11 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
11 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
11 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
11 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
11 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
11 |
|
S1 |
TE |
Friday |
10-12 |
U26 |
11 |
|
Show entire timetable
Show personal time table for this course.
Revison of timetable:
: Ændringer i skema onsdag uge 09 pga. Valg Undervejs.
Comment:
Ubegrænset deltagerantal. 3. kvartal
Prerequisites:
None
Academic preconditions:
The content of DM507 Algorithms and Data Structures and DM528 Combinatorics, Probability and Randomized Algorithms.
Course introductionThe purpose of the course is:
1. To give the students knowledge of methods for developing and analysing efficient algorithms.
2. To give the students knowledge of the complexity of algorithms and certain aspects of complexity theory.
QualificationsThe 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 outcomeAfter 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 overviewLower 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.