Algorithmics (ALG)

Widen the range of algorithmic techniques and deepen into its theoretical base. Deepen into the design and evaluation of algorithms. Present the probabilistic algorithms as an algorithm design tool. Present algorithmic tools to deal with computationally difficult problems, like approximation algorithms and local search based methods. Present the algorithmic engineering as a selection of the data structures and the most suitable algorithmic techniques for solving a concrete problem.

Knowledges

1. Analysis of algorithms: efficiency, costs, asymptotic notation. Recurrences. Analysis of the average case.
2. Theoretical foundation of algorithmic schemes.
3. Advanced algorithms for basic problems: ordering, graphs, hashing.
4. Random algorithms: Types, technical elements of design. Primeness. Analytical techniques.
5. Approximation algorithms: Approximation concept. Efficiency versus quality. Analysis and design techniques.
6. Local search based methods: Local search and its variations. Experimental evaluation.
7. Metaheuristics: methods for the approximate solution of combinatorial and continuous optimization problems.

Abilities

1. Ability to use advanced techniques for designing and analyzing algorithms.
2. Knowing how to reason the correctness and efficiency of probabilistic algorithms.
3. Knowledge of some of the classic algorithms for dealing with basic problems.
4. Knowing how to identify the most relevant items of a problem and choose the most appropriate algorithmic approach to solve it.
5. Knowing how to choose the data types that most enhance a given algorithmic solution.

Competences

1. Critical, logical-mathematical reasoning.
2. Ability to solve problems through the application of scientific and engineering methods.
3. Ability to design systems, components and processes meeting certain needs, using the most appropriate methods, techniques and tools in each case.
4. Ability to think in abstract terms. Ability to tackle new problems by consciously using strategies that have proved useful in solving previous problems.
5. Ability to study various sources, recognise that the information obtained in class is insufficient, and to seek the supplementary information required.
6. Ability to relate and structure information from various sources and thus integrate ideas and knowledge.
7. Ability to effectively convey one"s ideas in writing.
8. Willingness and ability to update one"s professional knowledge throughout one"s career.

There will be two kinds of classes: theoretical sessions and practical sessions. On average, three hours a week is dedicated to theory and two hours a week to exercises. The teacher will allocate the hours in accordance with the subject matter.

The theory classes take the form of lectures in which the teacher sets out new concepts or techniques and examples illustrating them.

The practical classes are used to carry out exercises in which students take an active part. Teachers set the exercises in advance. Students are required to submit the exercises and then discuss the various solutions/alternatives in class.

Written submission at problem sessions (Pro). Final exam (Fin).

The final grade will be calculated in accordance with the following formula:

max(Fin, 0.7 * Fin + 0.3*Pro).

• Thomas H. Cormen ... [et al.] Introduction to algorithms, MIT Press, 2001.
• Jon Kleinberg, Éva Tardos Algorithm design, Pearson/Addison-Wesley, 2006.
• Michael Mitzenmacher, Eli Upfal Probability and computing : randomized algorithms and probabilistic analysis, Cambridge University Press, 2005.
• Vijay V. Vazirani Approximation algorithms, Springer, 2003.
• Holger H. Hoos, Thomas Stützle Stochastic local research : foundations and applications, Morgan Kaufmann Publishers, 2005.

• FERRI, F. J., ALBERT, J. V., MARTÍN, G. Introducció a l'anàlisi i disseny d'algorismes, Universitat de València, 1998.
• MOTWANI, R. i RAGHAVAN, P. Randomized Algorithms, Cambridge University Press, 1995.
• Steven S. Skiena The Algorithm design manual, TELOS--the Electronic Library of Science, 1998.
• Michael R. Garey, David S. Johnson Computers and intractability : a guide to the theory of NP-Completeness, W.H. Freeman, 1979.
• Zbigniew Michalewicz, David B. Fogel How to solve it : modern heuristics, Springer,, 2004.

Basic background on analysis and design of algorithms