NDAA09023U  Advanced Algorithms and Data Structures (AADS)

Volume 2017/2018
Education

MSc Programme in Computer Science

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 specialized elective courses.

Learning Outcome

Knowledge of:

  • Graph algorithms such as max flow.
  • Data structures such as Fibonacci heaps.
  • NP-completeness.
  • Exponential and parameterized algorithms for NP-hard problems.
  • Approximation algorithms.
  • Randomized algorithms.
  • Computational geometry.
  • Linear programming and optimization.

 

Skills to:

  • Analyze algorithms with respect to correctness and efficiency.
  • Explain and use basic randomized algorithms.
  • Recognize 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:

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

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).
A mix of lectures and exercises.
Credit
7,5 ECTS
Type of assessment
Oral examination, 30 minutes
Oral exam with preparation (30 minutes) in course curriculum.
Exam registration requirements

The student must solve the 2 mandatory exercises during the course. The exercises must be submitted and approved by the due date in order to qualify for the exam.

Aid
All aids allowed
Marking scale
7-point grading scale
Censorship form
External censorship
Re-exam

Re-exam same as ordinary exam.

If the student is not yet qualified, then qualification can be achieved by handing-in equivalent exercises. The equivalent exercises must be submitted and approved no later than two weeks before the re-exam date in order to qualify for the exam.

 

Criteria for exam assesment

See learning outcome.

  • Category
  • Hours
  • Lectures
  • 36
  • Theory exercises
  • 84
  • Preparation
  • 84
  • Exam
  • 2
  • Total
  • 206