COMPETENCIES

M09CM07 - To select the most appropriate algorithm design techniques for solving each problem.

M09CM08 - To study the computational costs of algorithms.

M09CM09 - To propose valid alternatives based on the problem specifications and / or on the limitations on the algorithms.

M09CM10 - To propose effective implementations.

LEARNING OUTCOMES

The student must know the fundamental methods of algorithm design and be able to choose the appropriate algorithmic techniques for solving the proposed problems, as well as carry out comparative analysis based on specifications and objectives. He/she must also be capable of designing efficient implementations as well as estimating and analyzing their computational costs. The students must also be able to perform analyses of real costs on a computer. Finally, they must communicate ideas and results related to the subject both orally and in writing.

1. INTRODUCTION: efficiency of algorithms, spatial and temporal complexities, analysis of recursive algorithms, review of basic techniques.

2. STATE-SPACE SEARCH ALGORITHMS: general schema, Depth First Search, Backtracking, Branch and Bound.

3. INFORMED SEARCH: heuristics and evaluation functions, optimal search, A* algorithm.

4. GREEDY ALGORITHMS: general schema, Prim algorithm, Kruskal algorithm, Dijkstra algorithm, applications to technological problems.

5. DYNAMIC PROGRAMMING: general recursive and iterative schemas, Principle of Optimality, Minimum Paths, Applications to technological problems.



COMPUTER PRACTICES

P0.- Selection and verification of the programming environment

P1.- Analysis of Iterative and recursive algorithms.

P2.- Depth first search (backtracking); branch and bound

P3.- Decision algorithms in zero-sum games.

P4.- Optimization problems: A* algorithm, greedy algorithms and dynamic programming.

The theoretical content will be exposed in master classes that follow basic references that appear in the Bibliography and in the material of obligatory use. These master classes will be complemented with problem classes (classroom practices) in which students will be asked to solve questions and exercises and thus the knowledge acquired in the theoretical classes will be applied. In the seminars, the students will make presentations of questions and examples related to the content of the course. In addition, there will be computer practices aimed at achieving the practical skills defined in the subject.

Continuous assessment:

- Presentations in Seminars: 15%

- Algorithmic resolution of proposed problems: individual exercises to be delivered along with a written exam (15%) and a final exam (45%).

- Individual Practice Work (Computer Practices): reports to be delivered and an additional verification on the computer 25%

A minimum score of 4/10 is required at each evaluation element.

Final Evaluation in the Ordinary Call:

- Algorithmic resolution of proposed problems (exam): 75%

- Individual Practice Work (Computer Practices): reports to be delivered and an additional verification on the computer 25%

A minimum score of 4/10 is required at each evaluation element.

If the sanitary conditions recommend to remove in-person exams then distance procedures will be activated. Students will be informed through the eGela platform.

Phyton programming language.
Course slides and some basic books.

Basic bibliography

- Gilles Brassard, Paul Bratley. Fundamentos de algoritmia. Prentice-Hall, 2006.

- Ian Parberry. Problems on Algorithms (Second Edition). Prentice Hall, 2002.

- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorit ms (Third Edition). The MIT Press, 2009.

- Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran. Computer algorithms (second Edition). Universities Press, 2007.

- Francesc J. Ferri, Jesús v. Albert, Gregorio Martín, Introducció a l'anàlisi i disseny d'algorismes, Universitat de Valencia, 1998

- Robert Sedgewick an Kevin Wayne: Algorithms (Fourth Edition).

- Steven S. Skiena. The Algorithm Design Manual (Second Edition). Springer, 2008.

In-depth bibliography

- Jason Brownlee: Clever Algorithms: Nature-Inspired Programming Recipes. lulu.com, 2012
- Weixiong Zhang: State-Space Search. Algorithms, Complexity, Extensions and Applications. Springer 1999,
- Bo Xing and Wen-Jing Gao. Innovative Computational Intelligence: A Rough Guide to 134 Clever Algorithms. Springer 2014.