Person in charge:  () 
Others:  () 
Credits  Dept. 

7.5 (6.0 ECTS)  CS 
Person in charge:  () 
Others:  () 
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.
Estimated time (hours):
T  P  L  Alt  Ext. L  Stu  A. time 
Theory  Problems  Laboratory  Other activities  External Laboratory  Study  Additional time 

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. 

T  P  L  Alt  Ext. L  Stu  A. time  Total  

8,0  7,0  0  0  0  13,0  0  28,0  
Shortests paths. BellmanFord, FloydWarshall and Johnson algorithms. Max Flow and Matching algorithms. Linear programming.


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. MonteCarlo and Las Vegas algorithms. Probability amplification. Concentration measures. Some examples in the analysis of randomized algorithms. Random walks. Web algorithms.
MonteCarlo and Las Vegas algorithms. Extension of probability. Primality test. Concentration points. Examples in the analysis of random 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.


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


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 
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).
Basic background on analysis and design of algorithms