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
Common	I	Monday	12-14	U140	5-7,9-11,14-19
Common	I	Tuesday	14-16	U48A	13
Common	I	Tuesday	14-16	U140	19
Common	I	Wednesday	14-16	U140	6
Common	I	Thursday	08-10	U140	5,13,15,17,20
Common	I	Friday	12-15	U48A	22
D2	TE	Tuesday	14-16	U155	5,9-10,14-15,17
D2	TE	Tuesday	14-16	U27A	6-7,11
D2	TE	Tuesday	16-18	U152	16,19
D2	TE	Tuesday	14-16	U156	18
D2	TE	Tuesday	10-12	U14	21
D2	TE	Wednesday	14-16	U27A	13
D2	TE	Thursday	10-12	U155	6,9,11,14,16,20
D2	TE	Friday	14-16	U14	18
D3	TE	Monday	08-10	U31	6,9,11,14,18
D3	TE	Monday	16-18	U14	16
D3	TE	Tuesday	08-10	U26A	5-7,9-11,13-15
D3	TE	Tuesday	08-10	U14	18,21
D3	TE	Wednesday	16-18	U152	16-17,19-20
O1	TE	Monday	08-10	U10	21
O1	TE	Tuesday	10-12	U146	5-7,9-11,13-19
O1	TE	Wednesday	14-16	U141	9
O1	TE	Thursday	08-10	U154	6,16
O1	TE	Thursday	14-16	U56	11,14
O1	TE	Friday	10-12	U10	18,20
T1	TE	Monday	14-16	U14	16,19
T1	TE	Monday	12-14	U154	21
T1	TE	Tuesday	12-14	U146	5-6
T1	TE	Tuesday	12-14	U14	7,10
T1	TE	Tuesday	12-14	U31	9,13-15
T1	TE	Tuesday	12-14	U26A	11,16
T1	TE	Tuesday	12-14	U56	17
T1	TE	Tuesday	12-14	U50A	18
T1	TE	Friday	12-14	U74	6
T1	TE	Friday	12-14	U56	9,11
T1	TE	Friday	12-14	U51	14,18
T1	TE	Friday	12-14	U31	20

Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal.

Prerequisites:
None

Academic preconditions:
Knowledge of the contents of DM550 Introduction to Programming is necessary. Knowledge of the contents of DM549 Discrete Methods for Computer Science is recommended.

Course introduction
To acquaint the students with a wide range of fundamental algorithms and data structures. Furthermore, we introduce general methods for development of algorithms, as well as mathematical tools for analyzing the correctness and efficiency of algorithms.

Expected learning outcome
After the course, the student is expected to be able 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 4 items.

Subject overview
Mathematical basis: recursion equations.

Algorithms: correctness and complexity analysis, greedy algorithms, divide and conquer, dynamic programming, sorting, graph algorithms, Huffmann-coding.

Data structures: trees, dictionaries, priority queues, disjoint sets.

Literature

Meddeles 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:
A 4 hour written exam where books, notes and calculators may be used. External examiner. Grades according to the 7-point marking scale. (15016702)

Reexam after 4th quarter in August. The reexam 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

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.