Courses NonDegree Display 2020-2021
| Course Description | To PDF | |||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Course title | Algorithms and Optimisation | |||||||||||||||||||||||||||||||||||||||
| Course code | EBC4049 | |||||||||||||||||||||||||||||||||||||||
| ECTS credits | 6,5 | |||||||||||||||||||||||||||||||||||||||
| Assessment | Whole/Half Grades | |||||||||||||||||||||||||||||||||||||||
| Period |
|
|||||||||||||||||||||||||||||||||||||||
| Level | Advanced | |||||||||||||||||||||||||||||||||||||||
| Coordinator |
Stan van Hoesel, Tom van der Zanden For more information: s.vanhoesel@maastrichtuniversity.nl; t.vanderzanden@maastrichtuniversity.nl |
|||||||||||||||||||||||||||||||||||||||
| Language of instruction | English | |||||||||||||||||||||||||||||||||||||||
| Goals |
Ability to analyse the complexity of optimization problems, and ability to design fast algorithms providing good-quality solutions for hard optimization problems.
|
|||||||||||||||||||||||||||||||||||||||
| Description |
PLEASE NOTE THAT THE INFORMATION ABOUT THE TEACHING AND ASSESSMENT METHOD(S) USED IN THIS COURSE IS WITH RESERVATION. THE INFORMATION PROVIDED HERE IS BASED ON THE COURSE SETUP PRIOR TO THE CORONAVIRUS CRISIS. AS A CONSEQUENCE OF THE CRISIS, COURSE COORDINATORS MAY BE FORCED TO CHANGE THE TEACHING AND ASSESSMENT METHODS USED. THE MOST UP-TO-DATE INFORMATION ABOUT THE TEACHING/ASSESSMENT METHOD(S) WILL BE AVAILABLE IN THE COURSE SYLLABUS.
This course is devoted to mathematical models and solution methods for hard optimization problems. First, we study the theory of computational complexity, including the concept of P versus NP. In particular, we prove that some problems are computationally intractable. Given the complexity insights, solving such problems is a challenge. Therefore, we study the design and analysis of exponential time exact algorithms as well as polynomial time approximation algorithms and approximation scheme. The course is open ended in the sense that some topics can be chosen according to student interests. Classical problems that will be covered are, among others, scheduling, colouring, set covering, and packing equired algorithm design skills will be used to solve challenging problems from Project Euler (projecteuler.net) throughout the entire course. |
|||||||||||||||||||||||||||||||||||||||
| Literature |
"Algorithms" by Dasgupta, Papadimitriou and Vazirani (Mc Graw-Hill).
Selected chapters from several books on combinatorial optimization. |
|||||||||||||||||||||||||||||||||||||||
| Prerequisites |
Students need to have obtained a Bachelor degree in Econometrics, Operations Research, Mathematics, or Computer Science. Knowledge in optimization (Linear Programming) and basic graph theory is highly recommended. Familiarity with basic algorithms and the analysis of algorithms (runtime complexity) is certainly helpful. C++ (or Java/Python/Basic) Programming skills are also prerequisites as there will be many practical programming cases.
An advanced level of English. |
|||||||||||||||||||||||||||||||||||||||
| Teaching methods (indicative; course manual is definitive) | PBL / Lecture / Assignment / Groupwork | |||||||||||||||||||||||||||||||||||||||
| Assessment methods (indicative; course manual is definitive) | Participation / Take home exam | |||||||||||||||||||||||||||||||||||||||
| Evaluation in previous academic year | For the complete evaluation of this course please click "here" | |||||||||||||||||||||||||||||||||||||||
| This course belongs to the following programmes / specialisations |
|