NDAK16001U Approximation Algorithms (APX)
MSc Programme in Computer Science
Many optimization problems in the real world are NP-hard, meaning that we cannot hope to solve them optimally. Instead, we use approximation algorithms to find solutions that are provably close in quality to the optimal solutions.
The course is of a theoretical nature, giving the students general guidelines for developing and analysing approximation algorithms for various optimization problems. It is aimed at graduate students who like to use mathematics to solve algorithmic problems.
The topics mentioned under Learning Outcome are covered in lectures and worked on in exercises in order to develop the necessary skills and competences.
Knowledge of
- Greedy algorithms and local search
- Rounding data and dynamic programming
- Deterministic rounding of linear programs
- Random sampling and randomized rounding of linear programs
- Randomized rounding of semidefinite programs
- The primal-dual method
- Cuts and metrics
Skills in
- Proving approximation guarantees for different types of algorithms
- Using linear programming, both with rounding and as a theoretical basis for primal-dual algorithms
- Analysing greedy algorithms and local search algorithms
Competences to
- Apply approximation algorithms to computational problems that the student may later encounter in life.
- Communicate effectively about the theory of approximation algorithms, both for accessing advanced topics from the research literature and for convincingly presenting the results of own work.
See Absalon when the course is set up.
Expected to be: "The Design of Approximation Algorithms" by Shmoys and Williamson (is available for free online)
Academic qualifications equivalent to a BSc degree is recommended.
- Category
- Hours
- Lectures
- 36
- Preparation
- 85
- Theory exercises
- 84
- Exam
- 1
- Total
- 206
As
an exchange, guest and credit student - click here!
Continuing Education - click here!
PhD’s can register for MSc-course by following the same procedure as credit-students, see link above.
- Credit
- 7,5 ECTS
- Type of assessment
- Oral examination, 30 minutes (including grading)The oral examination is with 30 minutes preparation
- Exam registration requirements
The student must solve mandatory assignments during the course. Assignments will be made each week and be due in the following week. 4 out of 6 assignments must be submitted timely and approved in order to qualify for the exam.
- Aid
- All aids allowed
- Marking scale
- 7-point grading scale
- Censorship form
- No external censorship
Several internal examiners
- Re-exam
Re-exam same as the ordinary exam.
If the student is not yet qualified to participating in the exam, then qualification can be achieved by handing-in the missing/not-approved assignments. The missing/not-approved assignments must be submitted and approved no later than three weeks before the re-exam week in order to qualify for the re-exam.
Criteria for exam assesment
See Learning Outcome.
Course information
- Language
- English
- Course code
- NDAK16001U
- Credit
- 7,5 ECTS
- Level
- Full Degree Master
- Duration
- 1 block
- Placement
- Block 4
- Schedule
- A
- Course capacity
- No limit
- Course is also available as continuing and professional education
- Study board
- Study Board of Mathematics and Computer Science
Contracting department
- Department of Computer Science
Contracting faculty
- Faculty of Science
Course Coordinators
- Rasmus Pagh (pagh@di.ku.dk)
Lecturers
Thomas Dueholm Hansen
Mikkel Abrahamsen