Design of Algorithms for Optimization Problems
Code
11556
Academic unit
Faculdade de Ciências e Tecnologia
Department
Departamento de Informática
Credits
6.0
Teacher in charge
Margarida Paula Neves Mamede, Pedro Manuel Corrêa Calvente Barahona
Weekly hours
4
Total hours
55
Teaching language
Inglês
Objectives
Knowledge
Define and identify approximation, randomized and local search algorithms.
Know some general methods for designing approximation, randomized and local search algorithms.
Understand heuristics and meta-heuristics.
Application
Design an approximation algorithm, a randomized algorithm, and a local search algorithm for a real-world optimization problem.
Calculate the approximation ratio of an approximation algorithm.
Perform the probabilistic analysis of a randomized algorithm.
Select the suitable techniques to solve a problem.
Soft-skills
Skills in research and autonomy.
Prerequisites
Students should:
(a) be proficient in programming;
(b) be familiar with the fundamental data structures (linked lists, hash tables, binary search trees, binary heaps);
(c) be able to calculate the time and the space complexities of algorithms;
(d) know the basic concepts of the Theory of Complexity.
(e) know the basic concepts of search in state spaces.
Subject matter
(1) Decision problems and optimization problems. Tractable problems and hard problems. Algorithm design techniques for hard optimization problems.
(2) Approximation algorithms. Approximation ratio. Greedy strategies. The primal-dual and the primal methods. Approximation schemes.
(3) Randomised approximation algorithms. Probabilistic analysis.
(4) Local search algorithms. Restarts. Taboo search. Simulated annealing. Variable neighbourhood search. Large neighbourhood search. Ant colony optimization.
Bibliography
Main References
Jon Kleinberg and Éva Tardos. Algorithm Design. Addison-Wesley, 2006.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3rd edition). The MIT Press, 2009.
Pascal van Hentenryck and Laurent Michel, Constraint-Based Local Search, MIT Press, 2005.
Complementary References
Anany Levitin. Introduction to The Design and Analysis of Algorithms (3rd edition). Addison-Wesley, 2011.
Michael R. Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman and Company, 1979.
Teaching method
There are two hours of lectures and a lab session each week. In the laboratory, students design, analyse and implement algorithms.
Evaluation method
Assessment comprises one programming project and two tests.
The programming project is developed in two phases, whose deadlines are distinct, and consists of a theoretical and experimental comparative study of alternative solutions for an optimization problem, including the writing of two reports (one on each phase) and in a discussion. The tests and the exam are open-book.
Condition to succeed:
Pgrade >= 9 and Tgrade >= 9 and Fgrade = (Pgrade + Tgrade) / 2 >= 10,
where
- Pgrade is the project grade, calculated with the two phase grades;
- Tgrade is the mean of the test grades or the exam grade;
- Fgrade is the final grade.
In case of failure, if the project grade is not less than 9 (out of 20), students can do a final exam, whose grade replaces the previous Tgrade.