Algorithmics is the science that studies algorithms, their properties and their efficiency. Algorithmics aims at developing methods and techniques for designing efficient algorithms and data structures (DS) and for their analysis; another goal is the development of algorithms and DS that solve specific problems. After a brief review of basic concepts and known algorithmic techniques, we will study new techniques such as the greedy method, dynamic programming, network flows, linear programming and randomization. Each of the studied design and analysis techniques is illustrated with specific examples, many of which are fundamental algorithms and DS with significant practical impact such as Dijkstra's algorithm to compute the shortest paths in a graph, the algorithm to compute the edit distance between two strings, Rabin's primality test or Ford-Fulkerson algorithm to find the optimal flow in a network.
Person in charge
Maria Jose Serna Iglesias (
Conrado Martínez Parra (
Maria Josep Blesa Aguilera (
Common technical competencies
CT1 - To demonstrate knowledge and comprehension of essential facts, concepts, principles and theories related to informatics and their disciplines of reference.
- To use properly theories, procedures and tools in the professional development of the informatics engineering in all its fields (specification, design, implementation, deployment and products evaluation) demonstrating the comprehension of the adopted compromises in the design decisions.
CT4 - To demonstrate knowledge and capacity to apply the basic algorithmic procedures of the computer science technologies to design solutions for problems, analysing the suitability and complexity of the algorithms.
- To identify the most adequate algorithmic solutions to solve medium difficulty problems.
- To reason about the correction and efficiency of an algorithmic solution.
CT5 - To analyse, design, build and maintain applications in a robust, secure and efficient way, choosing the most adequate paradigm and programming languages.
- To know, design and use efficiently the most adequate data types and data structures to solve a problem.
- To design, write, test, refine, document and maintain code in an high level programming language to solve programming problems applying algorithmic schemas and using data structures.
- To design the programs¿ architecture using techniques of object orientation, modularization and specification and implementation of abstract data types.
G7 [Avaluable] - To detect deficiencies in the own knowledge and overcome them through critical reflection and choosing the best actuation to extend this knowledge. Capacity for learning new methods and technologies, and versatility to adapt oneself to new situations.
- Autonomous learning: capacity to plan and organize personal work. To apply the acquired knowledge when performing a task, in function of its suitability and importance, decide how to perform it and the needed time, and select the most adequate information sources. To identify the importance of establishing and maintaining contacts with students, teacher staff and professionals (networking). To identify information forums about ICT engineering, its advances and its impact in the society (IEEE, associations, etc.).
Technical Competences of each Specialization
Computer science specialization
CCO1 - To have an in-depth knowledge about the fundamental principles and computations models and be able to apply them to interpret, select, value, model and create new concepts, theories, uses and technological developments, related to informatics.
- To evaluate the computational complexity of a problem, know the algorithmic strategies which can solve it and recommend, develop and implement the solution which guarantees the best performance according to the established requirements.
CCO2 - To develop effectively and efficiently the adequate algorithms and software to solve complex computation problems.
- To implement information retrieval software.
CCO3 - To develop computer solutions that, taking into account the execution environment and the computer architecture where they are executed, achieve the best performance.
- To implement critical code following criteria like execution time, efficiency and security.
- To program taking into account the hardware architecture, using assembly language as well as high-level programming languages.
Knowing greedy algorithms, to identify when and how you can apply them, knowing the most common techniques to prove correctness and becoming familiar with some basic greedy algorithms, e.g, Dijkstra's algorithm, Kruskal's and Prim's algorithms.
Understanding the dynamic programming scheme, to identify when and how you can apply it and become familiar with some fundamental dynamic programming algorithms, eg, Floyd's algorithm or calculating the edit distance
Knowing the basic problem of optimal flows on networks, to become familiar with a basic algorithm (Ford-Fulkerson), to understand the maxflow-mincut theorem, to recognize when a problem can be formulated in terms of a flow problem
To understand the importance of randomization in the design of algorithms and data structures, to become familiar with some basic techniques of probabilistic analysis needed to study the efficiency of randomized algorithms and with some classic examples.
To know about some computational problems that arise in specific areas of CS as diverse as search in document databases,
protein and genomic databases, geographic information systems, content-based information retrieval, data compression, etc. and to know some advanced data structures to respond to these needs
Becoming familiar with the use of algorithmic design principles for the design of data structures and to learn some essential techniques to obtain implementations which yield maximum efficiency and take advantage of the specific hardware features supporting the execution
To develop the necessary habits, attitudes and skills to be able to study, alone or in a team, a specific subject, making use of available sources of information (bibliography, web, ...) and to achieve the level of knowledge and compression of the subject which is enough to explain it to others, writing a summary and preparing a supplementary visual material
To understand some basic principles for the design of computational experiments and to learn basic techniques of data collection, validation and statistical analysis of the collected data, and how to draw conclusions, recognizing the need, usefulness and limitations of experimental studies in design and implementation of algorithms and data structures
Basic Algorithmic Concepts
Worst case analysis. Asymptotic Notation. Divide and conquer. Analysis of recursive algorithms. Linear sorting. Graph algorithms. Randomization.
The scheme for greedy algorithms. Task scheduling. Bellman-Ford' and Johnson's algorithms for shortest paths. Kruskal's and Prim's algorithms for minimum spanning trees. Union-find. Huffman codes.
Principle of optimality. Memoization. Floyd-Warshall algorithm for all-shortest paths. Traveling salesman problem. Knapsack problem. Other examples.
Basic concepts. Maxflow-mincut theorem. The Ford-Fulkerson algorithm. Applications: Matching and Edge disjoint paths. Duality.
Advanced Data Structures and Algorithms
A selection of some of the following algorithms and/or data structures (or others). Linear Programming. Fibonacci heaps. Hashing. Bloom Filters. Blockchains. Map Reduce. Random graphs. Page Rank.
Basic Algorithmic Concepts
To remind the basic concepts learnt in previous courses, and to become familiar with the terminology and notation that will be used throughout the course. Learn other basic algorithmic techniques.
Autonomous learning: - Study of theory and problems seen in class
- Resolution of the exercises in advance
The goal is to solve problems proposed by the teacher. The assignments must be done in group. There will be at least 4 days between the date on which the assignment are publicized and the problems class in which the solution has to be presented and one additional week to hand out the written resolution. You can expect to get one or two problems per setmana per a cada grup. Objectives:1234568 Contents:
The teacher makes a brief interview with each of the student teams to discuss the written documentation and audiovisual material delivered, find out how the activity has been developed over the course, finding out about planning issues, if there was any, finding out what mechanisms have been used to coordinate the parts of the work carried out by the team, etc.. The teacher assesses the degree of learning of the proposed subject by the students by means of short specific questions and the achievement of the activity goals Objectives:12345678 Week:
Final Exam/Second partial
15 (Outside class hours) Type:
Theory lectures will be magistral, with theoretical explanations from the teacher, interspersed with numerous examples. Students should actively participate with their questions and comments along these classes. Each week there will be two hours of lectures and two hours devoted to problems. In problem sessions, there will be disucssion of the solutions proposed by the students to the exercises posed by the teacher in advance (more complex assignments, with which the student has been able to work during the week, autonomously) or of the short exercises posed during the class to be worked by teams of two students or individually. Occasionally, the students could be required to expose their solutions to the rest of their mates.
To complement personal study and practical problem solving in paper, a programming project will be proposed. In the project, the student must design and encode programs in C++ that solve the proposed problems, for instance, to implement two (or more) algorithms that solve the same problem and to carry out experiments that allow to compare the performance of the algorithms, and at the same time, to compare these performances with the predictions of the theoretical analysis. Each student will have to develop the project in a team of two or three people.
This project will be used to assess the autonomous learning skills, as it will require the study of a particular subject, related with those in the course, but no exposed in any lecture.
The final grade (NF) is calculated from the note of the resolution of algorithmic problems (A), that of the first partial written tests (M) (subject corresponding to the 6 -7 first weeks of the course), second partial (E) (subject corresponding to the last 6-7 weeks of the course) and final exam (F) and the project note associated with autonomous learning (P) according to the formulas:
NF1 = 0.7 0.5 (M + E) + 0.1 A + 0.2 P
NF2 = 0.7 F + 0.1 A + 0.2 P
One week before the end of the semester each student with grade M> = 3 must choose to take the second partial or the final exam on the day assigned for the final exam in the academic calendar. In the first case NF = NF1 and in the second case NF = NF2. If M <3, NF = NF2.
The teacher will assess the degree of acquisition of the "Autonomous learning" skill from the score earned in a programming project that involves autonomous learning on the part of the students. The score P will be graded in a numerical scale from 0 to 10.
The qualitative grade for "Autonomous learning" is given according to the range in which the numerical grade falls: [0,5) => D, [5,6.5) => C, [6.5, 8.5) => B, [8.5, 10] => A
- Familiarity with the basic programming techniques and the programming language C + +: iterations, alternative, recursive functions, parameter passing, pointers, references, dynamic memory, classes, objects, methods, ...
- Knowledge of basic algorithmic concepts: efficiency of algorithms, asymptotic notation, graphs, graph traversals, data structures (lists, search trees, hashing, heaps, ...)
- Basic knowledge of discrete mathematics, linear algebra and calculus
- Basic knowledge of probability theory and statistics
- Basic knowledge of computer architecture and memory hierarchy
No hi ha modificacions respecte als continguts de la guia docent
No hi ha modificacions respecte a la metodologia de la guia docent. Les classes de teoria no presencial es complementaran amb activitats voluntàries que fomentin la participació en aquestes classes i l'assimilació dels continguts de l'assignatura.
El mètode d'avaluació es modifica per adaptar-se a les directrius de la FIB sobre exàmens parcials i finals. S'elimina el segon parcial i s'introdueix una component voluntària addicional.
La nota final (NF) es calcula a partir de la nota de la resolució de problemes algorísmics (A); la de participació a classe de teoria i en les activitats voluntàries que es proposin (V); la de les proves escrites: parcial (M), matèria correspondent a les 6-7 primeres setmanes del curs; a l'examen final (F); i a la nota del projecte associat a l'aprenentatge autònom (P).
Es calculen les notes:
NE = max(0.4 M + 0.6 F, F)
NF1 = 0.7 NE + 0.1 A + 0.2 P i
NF2 = 0.7 NE + 0.1 A + 0.2 P + 0.1 V.
Per als alumnes amb nota NE>= 3.5, la nota final es calcula com
NF = min(NF2, 10),
i quan NE < 3.5 com,
El mètode d'avaluació de la competència d'aprenentatge autònom no canvia.
En cas de cancel·lació de tota activitat lectiva presencial les classes de problemes es continuaran de forma no presencial i es reforçaran amb eines de comunicació que permetin mantenir el contacte entre els estudiants i entre estudiants i professors de forma àgil, de forma síncrona o no.
Els exàmens es realitzaran de forma no presencial, amb entrega a través del Racó i/o d'Atenea.
Where we are
B6 Building Campus Nord
C/Jordi Girona Salgado,1-3
08034 BARCELONA Spain
Tel: (+34) 93 401 70 00