Master's Programme in Computer Science is responsible for the course.
The course belongs to the Discrete Algorithms CSM12100 and Discrete Algorithms (elective) CSM22100 modules.
The course is available to students from other degree programmes.
CSM12101 Algorithm Design and Analysis
Courses in the Discrete Algorithms study module.
Provides prerequisite knowledge for CSM12106 Approximation algorithms.
Recommended further studies: Automated reasoning
Explains properties of and connection between decision, search, enumeration, and optimization problems. Gives examples of polynomial-time and NP-hard optimization problems. Describes distinctive characteristics of exhaustive and local search style optimization algorithms. Describes some tractable classes of NP hard optimization problems. Describes distinctive characteristics of different declarative NP optimization languages and algorithms for them. Simulates the Simplex algorithm for solving linear programming instances. Derives dual formulations of integer programs. Derives different integer programming relaxations and cutting planes. Explains integer programming duality. Simulates branch-and-bound and branch-and-cut search. Develops domain-specific branch-and-bound algorithms for different NP hard problems. Encodes NP optimization problems compactly using integer programs and declarative NP Boolean optimization languages. Applies declarative optimization solvers to solve instances of NP-hard optimization problems.
Recommended time/stage of studies for completion:
1st or 2nd year of MSc studies.
After CSM12101 Algorithm Design and Analysis.
Term/teaching period when the course will be offered:
Autumn term, period II, biannually (first time in Autumn 2018)
Combinatorial search spaces, polynomial-time and NP-hard optimization problems. Linear programming and integer programming. Integer linear programming duality and relaxations. Cutting planes. Branch-and-bound and branch-and-cut. Finite-domain constraint optimization, Boolean optimization, maximum satisfiability. Stochastic local search.
The course does not follow any textbook directly.
Lecture slides and tutorials. A list of recommended supplementary literature will be provided when the course begins.
The course activities may vary per instantiation of the course.
The core study material consists of online lecture materials. Weekly lectures present the core study material with additional explanation and examples. Active participation in the lectures by the students is encouraged to support learning.
Students are given exercise problems geared towards learning the knowledge and skills described in the learning outcomes. Students present their solutions in weekly tutorials either in person or in electronic form (as instructed in the individual exercise sheets) and discuss them with a teacher to obtain feedback. The exercise problems may range from theoretical problems to implementation-level tasks.
Homework assignments (passed), final grade based on final exam, grading scale 0-5.
Contact teaching consisting of 2x 2 h lectures and 1x 2 h tutorials weekly. Other forms of activities, such as programming tasks as homework, are also possible.
Completion requirements: homework and final exam.