DM507: Algorithms and Data Structures
Study Board of Science
Teaching language: Danish or English depending on the teacher
EKA: N330046112, N330046102
Assessment: Second examiner: None, Second examiner: External
Grading: Pass/Fail, 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Bachelor
STADS ID (UVA): N330046101
ECTS value: 10
Date of Approval: 02-10-2019
Duration: 1 semester
Version: Archive
Comment
Entry requirements
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 introduction
The 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.
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 outcome
The 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.
Content
The 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.
Literature
Examination regulations
Exam element a)
Timing
Spring
Tests
A mandatory project
EKA
N330046112
Assessment
Second examiner: None
Grading
Pass/Fail
Identification
Full name and SDU username
Language
Normally, the same as teaching language
Examination aids
To be announced during the course
ECTS value
2
Additional information
The prerequisite examination is a prerequisite for participation in exam element a)
Exam element b)
Timing
June
Tests
Written exam
EKA
N330046102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card
Language
Normally, the same as teaching language
Examination aids
Books, notes and calculators may be used. Internet are not allowed. A closer description of the exam rules will be posted under 'Course Information' on Blackboard.
ECTS value
8
Additional information
The reexam in August is an oral exam with external examiner and grades according to the 7-point grading scale.