Advanced Algorithms and Data Structures (AADS)

Course content

Algorithms is about finding scalable solutions to computational problems, and the reliance is only increasing as we enter the world of Big Data. We want algorithms that solve problems efficiently relative to the input size. Exponential time is hopeless. We generally want polynomial time, and for large problems we need linear time. Sometimes we employ data structures that represent the input so that queries about it can be answered very efficiently. In this mandatory course, we will study the list of algorithmic topics below. Some of these topics are covered in more depth in more specialised elective courses.

Education

MSc Programme in Computer Science

MSc Programme in Computer Science (part time)

MSc Programme in Computer Science with a minor subject

MSc Programme in Bioinformatics

Learning outcome

Knowledge of

  • Graph algorithms such as max flow.
  • Data structures such as van Emde Boas Trees.
  • NP-completeness.
  • Exponential and parameterised algorithms for NP-hard problems.
  • Approximation algorithms.
  • Randomised algorithms.
  • Computational geometry.
  • Linear programming and optimisation.

 

Skills to

  • Analyse algorithms with respect to correctness and efficiency.
  • Explain and use basic randomised algorithms.
  • Recognise NP-hard problems and address them, e.g., using approximation algorithms.
  • Explain and use algorithms for different abstract domains such as graphs and geometry.
  • Formulate real-life problems as algorithmic problems and solve them.

 

Competences to

  • Analyse a computational problem in order to find an appropriate algorithmic approach to solve it.

A mix of lectures and exercises.

See Absalon when the course is set up.

It is assumed that the students are familiar with basic algorithms (sorting, selection, minimum spanning trees, shortest paths) and data structures (lists, stacks, binary trees, search trees, heaps).

Academic qualifications equivalent to a BSc degree is recommended.

Written
Individual
Continuous feedback during the course
ECTS
7,5 ECTS
Type of assessment
Oral examination, 30 minutes
Type of assessment details
Oral examination in course curriculum with 30 minutes preparation
Aid
All aids allowed
Marking scale
7-point grading scale
Censorship form
External censorship
Criteria for exam assessment

See learning outcome.

Single subject courses (day)

  • Category
  • Hours
  • Lectures
  • 36
  • Preparation
  • 85
  • Theory exercises
  • 84
  • Exam
  • 1
  • English
  • 206

Kursusinformation

Language
English
Course number
NDAA09023U
ECTS
7,5 ECTS
Programme level
Full Degree Master
Duration

1 block

Placement
Block 2
Schedulegroup
C
Capacity
No limit
The number of seats may be reduced in the late registration period
Studyboard
Study Board of Mathematics and Computer Science
Contracting department
  • Department of Computer Science
Contracting faculty
  • Faculty of Science
Course Coordinator
  • Christian Wulff-Nilsen   (7-6d71716e71717c42666b306d7730666d)
Teacher

Mikkel Abrahamsen, Jacob Holm, Danupon Nanongkai, Pawel Winter, Christian Wulff-Nilsen

Saved on the 27-06-2022

Are you BA- or KA-student?

Are you bachelor- or kandidat-student, then find the course in the course catalog for students:

Courseinformation of students