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.
Teachers
Person in charge
Maria Jose Serna Iglesias (
)
Others
Amalia Duch Brown (
)
Conrado Martínez Parra (
)
Maria Josep Blesa Aguilera (
)
Santiago Marco Sola (
)
Weekly hours
Theory
2
Problems
2
Laboratory
0
Guided learning
0.4
Autonomous learning
5.6
Competences
Technical Competences
Common technical competencies
CT1 - To demonstrate knowledge and comprehension of essential facts, concepts, principles and theories related to informatics and their disciplines of reference.
CT1.2C
- 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.
CT4.1
- To identify the most adequate algorithmic solutions to solve medium difficulty problems.
CT4.2
- 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.
CT5.2
- To know, design and use efficiently the most adequate data types and data structures to solve a problem.
CT5.3
- 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.
CT5.4
- To design the programs¿ architecture using techniques of object orientation, modularization and specification and implementation of abstract data types.
Transversal Competences
Autonomous learning
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.
G7.3
- 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.
CCO1.1
- 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.
CCO2.5
- 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.
CCO3.1
- To implement critical code following criteria like execution time, efficiency and security.
CCO3.2
- To program taking into account the hardware architecture, using assembly language as well as high-level programming languages.
Objectives
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.
Related competences:
CT1.2C,
CCO1.1,
CT4.1,
CT4.2,
CT5.2,
G7.3,
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
Related competences:
CT1.2C,
CCO1.1,
CT4.1,
CT4.2,
CT5.2,
G7.3,
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
Related competences:
CT1.2C,
CCO1.1,
CT4.1,
CT4.2,
G7.3,
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.
Related competences:
CT1.2C,
CCO1.1,
CT4.1,
CT4.2,
G7.3,
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
Related competences:
CT1.2C,
CCO2.5,
CCO1.1,
CT4.1,
CT4.2,
CT5.2,
CCO3.1,
G7.3,
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
Related competences:
CT1.2C,
CCO1.1,
CT4.1,
CT4.2,
CT5.2,
CCO3.1,
CCO3.2,
G7.3,
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
Related competences:
G7.3,
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
Related competences:
CT4.1,
CT4.2,
CT5.2,
CT5.4,
CCO3.1,
CCO3.2,
G7.3,
CT5.3,
Contents
Basic Algorithmic Concepts
Worst case analysis. Asymptotic Notation. Divide and conquer. Analysis of recursive algorithms. Linear sorting. Graph algorithms. Randomization.
Greedy algorithms
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.
Dynamic Programming
Principle of optimality. Memoization. Floyd-Warshall algorithm for all-shortest paths. Traveling salesman problem. Knapsack problem. Other examples.
Network Flows
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.
Activities
ActivityEvaluation act
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 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:
6 (Outside class hours)
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 discussion 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-four students or individually. Occasionally, the students could be required to expose their solutions to the rest of their mates. During the course, written handouts of the solution of 3-4 problems will be required, these solutions will be corrected by other students.
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.
Evaluation methodology
The final grade (NF) is calculated from the mark of the resolution of algorithmic problems (A), the mark of the handout and corrections of problems (P), that of the mid term exam (M) (subject corresponding to the 6 -7 first weeks of the course), the final exam (F) and the project note associated with autonomous learning (P).
The final mark is obtained by the formula
Si (M+F)/2 < 3.5, NF = (M+F)/2
Si (M+F)/2 >= 3.5, NF = 0.5 max(0.5 M + 0.5 F, F) + 0.2 P + 0.2 E + 0.1 A
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