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

7.5 (6.0 ECTS)  CS 

PRAP
 Prerequisite for DIE , DCSYS PRED  Prerequisite for DIE , DCSYS PS  Prerequisite for DCSFW 
Person in charge:  () 
Others:  () 
This subject provides students with basic algorithmic techniques in order for them to be able to develop correct and efficient programs for solving advanced problems. These basic techniques encompass theoretical and practical knowledge, skills, experience and a critical mindset, all of which are based on solid theories and techniques that have been proven and are wellestablished.
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  2,0  0  0  0  5,0  0  10,0  
Mergesort
Quicksort Karatsuba Strassen Other examples 

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

7,0  8,0  0  0  0  15,0  0  30,0  
Heaps
Heapsort Extended priority queues Hash tables Binary search trees Balanced binary search trees 

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

3,0  2,0  0  0  0  7,0  0  12,0  
Representations
Paths Basic algorithms 

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

5,0  5,0  0  0  0  12,0  0  22,0  
The principles underlying greedy algorithms
Minimum spanning trees: Kruskal, Prim Shortest paths: Dijkstra Optimal prefix codes: Huffman Other examples 

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

5,0  5,0  0  0  0  12,0  0  22,0  
The principles underlying exhaustive search algorithms
Backtracking and branch and bound Examples Notions of complexity 

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

5,0  5,0  0  0  0  12,0  0  22,0  
The principles underlying dynamic programming algorithms
The optimality principle Recursive solutions featuring memoization and iterative algorithms Shortest paths: Floyd Edit distance Other examples 
Total per kind  T  P  L  Alt  Ext. L  Stu  A. time  Total 
33,0  32,0  0  0  0  73,0  0  138,0  
Avaluation additional hours  9,0  
Total work hours for student  147,0 
The subject will be set forth in a highly practical fashion and will be illustrated with many examples.
Theory and examples of application will be presented in an intertwined fashion along the course.
The average five hours per week of this course are distributed into
two blocks per week of two hours
each and a block of two hours every two weeks.
The partial exam (P) evaluates items 1 through 4.
The computer exam (M) asks to solve two problems on
from items 2, 4, 5 and 6.
The final exam (F) evaluates all the items.
The practical work volunteer (A) consists of
implementation of a player for one game.
The grade for the course is calculated as follows:
GRADE = min (10, max (P + 25% 25% 50% M + F 100% F) + 20% A)
The timing is as follows:
P is a mid course exam, M is at the end of the course
and F fater its end. A should delivered by the end of the course.
The review mechanism before the machine is
follows:
In front of the computer, students receive two
problems. A problem is defined with a
utterance, one or more sets of evidence and public,
maybe some code already implemented. When a study
If your solution to deliver one of
problems, the machine sends a judge in
short seconds, he returned the verdict on
behavior of your program. Students can
forward up to 10 solutions for the same
trouble. The teachers corrected the last
submission for each problem.
The mechanism of practical work is voluntary
follows:
After partial shipment of the sentence
practical volunteer work, which consist of
description of a game. Students seeking
carry out practical work must be voluntary
program a player for this game (ie,
implement a strategy to try to win the
game). Along with the statement, teachers
Also given the code for a simple player:
the "silly."
At the end of course, there will be a public confrontation
through a system of rounds that will include all
The players delivered by students and the fool.
In this confrontation will be deducted from a classification
and appoint a champion.
The notice of voluntary practical work is calculated
automatically from the position where
classification of linearly and ensuring that the
Champion has a 10 and all participants
earning the silly to have a minimum grade 5.
The players who will not win the stupid one
note 0.
The voluntary submission of practical work
implicitly accepts that if it finds that
been fraud in its execution, shall be the
points (instead of adding them) of the
subject.
Mastery of objectoriented programming techniques:
 passing parameters,
 classes,
 objects,
 methods,
 pointers,
 dynamic memory,
 genericity,
 use of standard classes.
Mastery of at least one objectoriented language, preferably C++.
Recursiveness.
The ADT concept.
Sequential ADTs:
 stacks,
 queues,
 lists with Points of Interest (POI),
 lists with iterators.
Use and internal implementation of sequential ADTs.
branched ADTs:
 binary tree,
 nary tree,
 general tree,
 paths.
Use and internal implementation of branched ADTs (Abstract Data Types).
Mathematical knowledge of graphs, sums, and limits. Discrete mathematics. Ability to reason mathematically and to follow mathematical reasoning.
Rudimentary knowledge of statistics and probability: probability space, events, distribution functions, random variables, expectation.