# Algorithmics (ALG)

Credits Dept.
7.5 (6.0 ECTS) CS

## Instructors

 Person in charge: (-) Others: (-)

## General goals

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.

## Specific goals

### 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.

## Contents

Estimated time (hours):

 T P L Alt Ext. L Stu A. time Theory Problems Laboratory Other activities External Laboratory Study Additional time

1. Basic concepts
T      P      L      Alt    Ext. L Stu    A. time Total
2,0 2,0 0 0 0 3,0 0 7,0
The role played by algorithms in computation. Algorithm analysis and design. Orders of magnitude. Recurrences. Master Theorem.

2. Algorithm schemes
T      P      L      Alt    Ext. L Stu    A. time Total
3,0 3,0 0 0 0 10,0 0 16,0
Greedy algorithms. Theoretical foundations. Applications.

Dynamic programming. Theoretical foundations. Applications.

3. Algorithms for graphs
T      P      L      Alt    Ext. L Stu    A. time Total
8,0 7,0 0 0 0 13,0 0 28,0
Shortests paths. Bellman-Ford, Floyd-Warshall and Johnson algorithms. Max Flow and Matching algorithms. Linear programming.

4. Random algorithms
T      P      L      Alt    Ext. L Stu    A. time Total
11,0 8,0 0 0 0 15,0 0 34,0
Review of probabilities. Verification of polynomial identities. Monte-Carlo and Las Vegas algorithms. Probability amplification. Concentration measures. Some examples in the analysis of randomized algorithms. Random walks. Web algorithms.

Monte-Carlo and Las Vegas algorithms. Extension of probability. Primality test. Concentration points. Examples in the analysis of random algorithms.

5. Approximation algorithms
T      P      L      Alt    Ext. L Stu    A. time Total
9,0 6,0 0 0 0 10,0 0 25,0
Approximability. Efficiency versus quality. Analysis and dessign techniques. Approximation schemas. Limits to the approximability of problems. Randomized rounding.

6. Local search based algorithms
T      P      L      Alt    Ext. L Stu    A. time Total
6,0 0 4,0 0 5,0 4,0 0 19,0
Solutions and search space. The foundations of local search. Hill Climbing. Probabilistic variations of local search: Metropolis and Simulated annealing. Experimental evaluation of the performance. Iterated local search. GRASP: Greedy randomized adaptive search procedures

7. Metaheuristics: methods for the approximate solution of continuous and combinatorial optimization problems.
T      P      L      Alt    Ext. L Stu    A. time Total
6,0 0 4,0 0 5,0 4,0 0 19,0
Ant colony optimization. Evolutionary algorithms
Hybridization of metaheuristics with exact methods. Experimental evaluation of metaheuristics

 Total per kind T P L Alt Ext. L Stu A. time Total 45,0 26,0 8,0 0 10,0 59,0 0 148,0 Avaluation additional hours 6,0 Total work hours for student 154,0

## Docent Methodolgy

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.

## Evaluation Methodgy

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

## Basic Bibliography

• 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.

## Complementary Bibliography

• 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.

(no available informacion)

## Previous capacities

Basic background on analysis and design of algorithms

Compartir