DM865: Heuristics and approximation algorithms
Comment
Entry requirements
Academic preconditions
- use algorithms and data structures
- assess the complexity of the algorithms with respect to running time and space consumption
- program
The contents of DM507 Algorithms and Datastructures and DM550 Introduction to Programming must be known. It is an advantage to know the contents of DM553 Complexity and Computability or DM508 Algorithms and Complexity and the contents of DM559 Linear and Integer Programming.
Course introduction
The course builds on the knowledge acquired in the courses DM550 Introduction to Programming and DM507 Algorithms and Data Structures. Reference to concepts from DM554 Linear and Integer Programming together with DM508 Algorithms and Complexity or DM553 Complexity and Computability can also occur during the course. The course provides a basis for a master thesis in which algorithms for discrete optimization must be designed, analysed and implemented.
In relation to the competence profile of the degree it is the explicit focus of the course to:
- Give the competence to plan and execute scientific projects at an high professional standard
- Give the competence to plan and carry out scientific projects at the high professional level including managing work and development situations that are complex, unpredictable and require new solutions
- Give the skills to describe, analyze and solve advanced computational problems using the learned models
- Give the skills to analyze the advantages and disadvantages of various algorithms, especially in terms of resource consumptions
- Give the skills to elucidate the hypotheses of qualified theoretical background and critically evaluate own and others' research and scientific models
- Give the skills to develop new variants of the methods learned where the specific problem requires
- Give the skills in communicating through a written report research based knowledge and discuss professional and scientific problems with peers
- Give the expertise in discrete optimization and solution methods from the international research front
Expected learning outcome
- design specialized versions of general purpose heuristics, greedy, local search and metaheuristics, for problems similar in nature to the ones seen in the course.
- develop a solution prototype in a local search framework.
- undertake an experimental analysis, report the results and draw sound conclusions based on them.
- describe the work done in an appropriate language, possibly including pseudocode.
- give an overview of the problems and techniques studied in the course.
- give a precise description and analysis of each of the algorithms studied in the course.
Content
- Combinatorial algorithms
- LP-based algorithms
- greedy algorithms
- (stochastic) local search algorithms
- metaheuristics
- set cover
- traveling salesman
- satisfiability
- scheduling
- bin-packing
- knapsack
Literature
Examination regulations
Exam element a)
Timing
Tests
Oral exam
EKA
Assessment
Grading
Identification
Language
Examination aids
ECTS value
Additional information
Oral exam based on:the theoretical part and two practical project assignments submitted earlier.
The examination form for re-examination may be different from the exam form at the regular exam.
Indicative number of lessons
Teaching Method
- Implementation of some of the algorithms taught in the course.