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 middle case.
2. Theoretical foundation of algorithmic schemes.
3. Advanced basic algorithms: ordering, graphs, hashing.
4. Random algorithms: Types, technical elements of design. Primeness. Analytical techniques.
5. Approximation algorithms: Approximation concept. Efficiency versus quality. Analysys and design techniques.
6. Local search based methods: Local search and its variations. Experimental evaluation.

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 three 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).

• CORMEN, Thomas H. et alt. Introduction to algorithms. 2nd edition, MIT Press i McGraw-Hill, 2001.
• KLEINBERG, Jon i TARDOS, Eva Algorithm design, Pearson/Addison Wesley, 2006.
• MITZENMACHER, Michael i UPFAL, Eli Probability and Computing. Randomized algorithms and Probabilistic Analysis, Cambridge University Press, 2005.
• VAZIRANI, Vijay V. Approximation Algorithms, Springer, 2001.
• HOOS, Holger H., STÚTZLE, Thomas Stochastic local search: Foundations and applications, Elsevier, 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.
• SKIENA, Steven The algorithm design manual, Springer Verlag, 1998.
• GAREY, M. R. i JHONSON, D. S. Computers and intractability. A guide to the NP-completeness. , W.H. Freema, 1979.
• MICHALEWICZ, Z. i FOGEL, D.B. How to solve it: Modern Heuristics, Springer, 2000.

Basic background on analysis and design of algorithms