The mathematical analysis of the algorithms is introduced and the tools are presented to calculate its cost. These foundations are used to study and analyse the design and the different implementations of several algorithms and fundamental data structures (stacks, queues, lists, priority queues, trees, binary search trees, balanced trees, hash tables and graphs) . The necessary tools are introduced to implement these data structures and their associated algorithms. Moreover, object orientation and the use of external libraries are examined in detail.
Person in charge
Jordi Cortadella Fortuny (
Jordi Petit Silvestre (
CE2 - To be able to program solutions to engineering problems: Design efficient algorithmic solutions to a given computational problem, implement them in the form of a robust, structured and maintainable program, and check the validity of the solution.
CT5 - Solvent use of information resources. Manage the acquisition, structuring, analysis and visualization of data and information in the field of specialty and critically evaluate the results of such management.
CT6 - Autonomous Learning. Detect deficiencies in one's own knowledge and overcome them through critical reflection and the choice of the best action to extend this knowledge.
CT7 - Third language. Know a third language, preferably English, with an adequate oral and written level and in line with the needs of graduates.
CB5 - That the students have developed those learning skills necessary to undertake later studies with a high degree of autonomy
Generic Technical Competences
CG1 - To design computer systems that integrate data of provenances and very diverse forms, create with them mathematical models, reason on these models and act accordingly, learning from experience.
CG2 - Choose and apply the most appropriate methods and techniques to a problem defined by data that represents a challenge for its volume, speed, variety or heterogeneity, including computer, mathematical, statistical and signal processing methods.
CG5 - To be able to draw on fundamental knowledge and sound work methodologies acquired during the studies to adapt to the new technological scenarios of the future.
Being able to design, analyze, implement algorithms that solve problems using algorithmic and programming techniques.
Abstract Data Types.
Specification and implementation. Abstraction, functional and data decomposition, information hiding and encapsulation. Object-oriented languages: classes and objects, private and public methods, constructors and destructors. Genericity. Examples: point, rectangle, rational numbers.
Cost in time and space. Worst, best and average case. Asymptotic notation. Analysis of the cost of iterative and recursive algorithms. Examples: insertion and selection sort, maximum subsequence sum, convex hull.
Divide and conquer.
Principles: partition into subproblems, recombination of solutions. Master theorem. Examples: binary search, merge sort, quick sort, quick select, finding the two closest points in a plane. Fast Fourier Transform (FFT).
Representation of data in memory. Pointers and references. Dynamic memory management (vector class). Memory layout of a program (code, stack, heap).
Operations, usage and implementations of stacks, queues, priority queues and lists.
Representations: adjacency matrices, adjacency lists and implicit representations. Depth-first search (DFS). Breadth-first search (BFS). Topological sort. Algorithms for shortest paths (Dijsktra, Bellman-Ford). Algorithms for minimum spanning trees (Prim and Kruskal). Algorithms for the maximum flow problem (Ford-Fulkerson).
Sets and dictionaries.
Trees and their representation. Binary trees and traversals (pre-order, post-order, in-order and level-order). Binary search trees and balanced trees: operations and implementation. Hashing.
The syllabus is presented in a very practical way, through the presentation of many examples.
The theory classes introduce all the necessary concepts and techniques, which are put into practice in the classes of problems and laboratory through a collection of problems and exercises in an automatic judge.
Every week, there are two hours of theory classes, one hour of problems and two hours of laboratory.
The course uses C++ and Python as programming languages.
The grade of the course is calculated based on a grade obtained from two laboratory projects (NL), a partial exam on the computer (NP), and a final exam consisting of two tests: one on paper (NF1) and the other on the computer (NF2).
The final grade is the maximum of:
* 0.2 NL + 0.25 NP + 0.25 NF1 + 0.3 NF2
* 0.2 NL + 0.4 NF1 + 0.4 NF2
Only those students that have attended the exams and who have not passed the course are eligible for the re-evaluation exam. The exam consists of two tests similar to the final exam: one on paper (R1) and the other on the computer (R2). In case of not attending any of the tests, the corresponding mark of the final exam will be maintained (NF1 or NF2).
In the case of re-evaluation, the final grade of the course is calculated as 0.2 NL + 0.4 R1 + 0.4 R2