DM507: Algorithms and Data Structures (10 ECTS)
STADS: 15016701
Level
Bachelor course
Teaching period
The course is offered in the spring semester.
Teacher responsible
Email: rolf@imada.sdu.dk
Timetable
Group |
Type |
Day |
Time |
Classroom |
Weeks |
Comment |
Common |
I |
Wednesday |
10-12 |
U140 |
6-14,16-20 |
|
Common |
I |
Thursday |
08-10 |
U140 |
6,8,10,17 |
|
Common |
I |
Thursday |
12-14 |
U140 |
12,14,19 |
|
H7 |
TE |
Monday |
10-12 |
U155 |
22 |
|
H7 |
TE |
Tuesday |
12-14 |
U31 |
13,18 |
|
H7 |
TE |
Wednesday |
12-14 |
U31 |
20 |
|
H7 |
TE |
Thursday |
14-16 |
U31 |
7,12-13,16,18-20 |
|
H7 |
TE |
Thursday |
14-16 |
U154 |
9 |
|
H7 |
TE |
Thursday |
14-16 |
U156 |
11 |
|
H7 |
TE |
Thursday |
14-16 |
U146 |
14 |
|
H7 |
TE |
Thursday |
10-12 |
U48 |
17 |
|
H7 |
TE |
Friday |
08-10 |
U155 |
6-11,16 |
|
H8 |
TE |
Tuesday |
14-16 |
T9 |
13,21 |
|
H8 |
TE |
Tuesday |
14-16 |
U145 |
16 |
|
H8 |
TE |
Tuesday |
14-16 |
U154 |
18 |
|
H8 |
TE |
Wednesday |
12-14 |
U148 |
7,9 |
|
H8 |
TE |
Wednesday |
12-14 |
T9 |
11,20 |
|
H8 |
TE |
Thursday |
10-12 |
U44 |
6,10 |
|
H8 |
TE |
Thursday |
10-12 |
U142 |
7,12 |
|
H8 |
TE |
Thursday |
10-12 |
U154 |
8-9,11,13-14,17-19 |
|
H8 |
TE |
Thursday |
10-12 |
U155 |
16 |
|
H8 |
TE |
Friday |
10-12 |
U146 |
20 |
|
M1 |
TE |
Tuesday |
14-16 |
U31 |
7,9,16 |
|
M1 |
TE |
Tuesday |
14-16 |
T9 |
11 |
|
M1 |
TE |
Tuesday |
14-16 |
U146 |
13,20 |
|
M1 |
TE |
Tuesday |
14-16 |
U44 |
18 |
|
M1 |
TE |
Thursday |
12-14 |
U31 |
18 |
|
M1 |
TE |
Thursday |
14-16 |
U20 |
19 |
|
M1 |
TE |
Friday |
12-14 |
U31 |
6,8 |
|
M1 |
TE |
Friday |
12-14 |
U69A |
7 |
|
M1 |
TE |
Friday |
12-14 |
U28 |
9 |
|
M1 |
TE |
Friday |
12-14 |
U143 |
10 |
|
M1 |
TE |
Friday |
12-14 |
U155 |
11-14,16-17,20-21 |
|
T1 |
TE |
Tuesday |
12-14 |
U163 |
7,9,11,16 |
|
T1 |
TE |
Wednesday |
12-14 |
U168 |
13 |
|
T1 |
TE |
Wednesday |
12-14 |
U182 |
18-19 |
|
T1 |
TE |
Wednesday |
12-14 |
U20 |
20-21 |
|
T1 |
TE |
Thursday |
12-14 |
U156 |
6 |
|
T1 |
TE |
Thursday |
08-10 |
U24 |
7 |
|
T1 |
TE |
Thursday |
12-14 |
U155 |
8 |
|
T1 |
TE |
Thursday |
08-10 |
T9 |
9,11 |
|
T1 |
TE |
Thursday |
12-14 |
U31 |
10 |
|
T1 |
TE |
Thursday |
08-10 |
U167 |
12 |
|
T1 |
TE |
Thursday |
08-10 |
U31 |
13,16,18 |
|
T1 |
TE |
Thursday |
08-10 |
U20 |
14 |
|
T1 |
TE |
Thursday |
08-10 |
U155 |
20 |
|
T1 |
TE |
Friday |
10-12 |
U168 |
17 |
|
Show entire timetable
Show personal time table for this course.
Comment:
Ubegrænset deltagerantal.
Prerequisites:
None
Academic preconditions:
Students taking the course are expected to:
- Have knowledge of the contents of DM549 Discrete Methods for Computer Science. In particular, some amount of mathematical maturity is assumed.
- Be able to use the methods from DM550 Introduction to Programming. In particular, familiarity with programming in Java is assumed.
Course introductionThe aim of the course is to enable the student to apply a wide range of existing algorithms and data structures for fundamental problems, as well as general methods for developing new algorithms and mathematical tools for analyzing the correctness and efficiency of algorithms. This is of paramount importance for the ability to develop efficient software, and is central to the understanding of upper and lower bounds for computational problems.
The course builds on the knowledge acquired in the courses DM549 Discrete Methods for Computer Science and DM550 Introduction to Programming, and gives an academic basis for studying the algorithmical and complexity theoretical topics that are part of the degree. In relation to the competence profile of the degree it is the explicit focus of the course to:
- Give the competence to develop new variants of central algorithms and data structures developed within computer science.
- Give skills to analyze pros and cons of algorithms, in particular with respect to the use of resources.
- Give knowledge and understanding of a selection of core algorithms and data structures developed within computer science.
Expected learning outcomeThe learning objective of the course is that the student demonstrates the ability to:
- use the algorithms taught in the course on concrete problem instances.
- give precise arguments for the correctness or incorrectness of an algorithm.
- determine the asymptotic running time of an algorithm.
- adapt known algorithms and data structures to special cases of known problems or new problems.
- design new algorithms for problems similar to those taught in the course. This includes giving a precise description of the algorithm, e.g. using pseudocode.
- make expedient choices of data structures.
- design new data structures based on known data structures.
- design and implement a larger program, using algorithms and data structures taught in the course.
- give precise arguments for the choices made in connection with the previous four items.
Subject overviewThe following main topics are contained in the course:
- Mathematical basis: recursion equations, invariants.
- Algorithms: correctness and complexity analysis, divide and conquer (Master Theorem, Strassen's algorithm), greedy algorithms, dynamic programming, sorting algorithms (insertionsort, mergesort, heapsort, quicksort, countingsort, radixsort), graph algorithms (BFS, DFS, topological sorting of DAGs, connected components, strongly connected components, MST, SSSP, APSP), Huffmann coding.
- Data structures: dictionaries (BSTs, red-black trees, hashing), priority queues, disjoint sets.
LiteratureMeddeles ved kursets start.
Website
This course uses
e-learn (blackboard).
Prerequisites for participating in the exam
- A mandatory project. Internal examiner. Passed/not passed. The project must be passed to in order to be admitted to the exam. (15016712).
Assessment and marking:
- Written exam where books, notes and calculators may be used. External examiner. Grades according to the 7-point marking scale. (10 ECTS). (15016702).
The reexam in August is an oral exam with external examiner and grades according to the 7-point grading scale.
Expected working hours
The teaching method is based on three phase model.
Intro phase: 44 hours
Skills training phase: 40 hours, hereof:
- Tutorials: 40 hours
Educational activities
Study phase: 14 hours
Educational form
- Exercises in study groups.
Language
This course is taught in Danish or English, depending on the lecturer.
Course enrollment
See deadline of enrolment.
Tuition fees for single courses
See fees for single courses.