NDAA09023U Advanced Algorithms and Data Structures (AADS)
MSc Programme in Computer Science
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.
- Graph algorithms such as max flow.
- Data structures such as van Emde Boas Trees.
- Exponential and parameterised algorithms for NP-hard problems.
- Approximation algorithms.
- Randomised algorithms.
- Computational geometry.
- Linear programming and optimisation.
- 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.
- Analyse a computational problem in order to find an appropriate algorithmic approach to solve it.
See Absalon when the course is set up.
Academic qualifications equivalent to a BSc degree is recommended.
- Theory exercises
PhD’s can register for MSc-course by following the same procedure as credit-students, see link above.
- 7,5 ECTS
- Type of assessment
- Oral examination, 30 minutesOral examination in course curriculum with 30 minutes preparation
- Exam registration requirements
The student must get 4 out of 5 weekly assignments approved by the due date in order to qualify for the exam.
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- External censorship
Re-exam same as ordinary exam.
If the student is not yet qualified for the exam, then qualification can be achieved by submitting equivalent assignments. The equivalent assignments must be approved no later than three weeks before the re-exam date in order to qualify for the exam.
Criteria for exam assesment
See learning outcome.