DS814: Algorithms and Data Structures
Study Board of Science
Teaching language: Danish or English depending on the teacher
EKA: N340127112, N340127102
Assessment: Second examiner: None, Second examiner: External
Grading: Pass/Fail, 7-point grading scale
Offered in: Odense
Offered in: Spring
Level: Master
STADS ID (UVA): N340127101
ECTS value: 10
Date of Approval: 28-10-2022
Duration: 1 semester
Version: Archive
Comment
Entry requirements
The course cannot be taken by students enrolled on a programme, where DM507 is mandatory, or by students who have chosen or passed DM507 as an elective.
The course cannot be taken by students enrolled in the master programme in Computer Science.
The course cannot be taken by students enrolled in the master programme in Computer Science.
Academic preconditions
Students taking the course are expected to:
- Have some amount of mathematical maturity.
- Be able to use
the methods from DS801 Introduction to object-oriented programming. In particular,
familiarity with programming in Java or Python 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 course DS801 Introduction to object-oriented 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, including 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
N340127112
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.5
Exam element b)
Timing
June
Tests
Written exam
EKA
N340127102
Assessment
Second examiner: External
Grading
7-point grading scale
Identification
Student Identification Card
Language
Normally, the same as teaching language
Duration
3 hours
Examination aids
All common aids are allowed e.g. books, notes, computer programmes which do not use internet etc.
Internet is not allowed during the exam. However, you may visit system DE-Digital Exam when answering the multiple-choice questions. If you wish to use course materials from itslearning, you must download the materials to your computer the day before the exam. During the exam itslearning is not allowed.
ECTS value
7.5
Additional information
The reexam in August is an oral exam with external examiner and grades according to the 7-point grading scale.
Indicative number of lessons
Teaching Method
Teaching activities are reflected in an estimated allocation of the workload of an average student as follows:
- Intro phase (lectures, class lessons) - 44 hours
- Training phase: 44 hours
Teaching method: Assignments in study groups.
Teacher responsible
Timetable
Administrative Unit
Team at Educational Law & Registration
Offered in
Recommended course of study
Transition rules
Transitional arrangements describe how a course replaces another course when changes are made to the course of study.
If a transitional arrangement has been made for a course, it will be stated in the list.
See transitional arrangements for all courses at the Faculty of Science.