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
Josep Diaz Cort (
)
M. Jose Blesa Aguilera (
)
Maria Del Carme Alvarez Faura (
)
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 - 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 such as the randomized quicksort, the skip list data structure,
Rabin primality test algorithm or the pattern matching algorithm for strings of Karp-Rabin
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:
CCO2.5,
CT1.2C,
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:
CT5.3,
CT4.1,
CT4.2,
CT5.2,
CT5.4,
CCO3.1,
CCO3.2,
G7.3,
Contents
Basic Algorithmic Concepts
Worst case analysis. Asymptotic Notation. Divide and conquer. Analysis of recursive algorithms. Hashing. 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 or others data structures together with associated algorithms. Fibonacci heaps. Cuckoo hashing. Bloom Filters. Blockchains. Map Reduce. Random graphs.
Activities
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.
Theory
6
Problems
6
Laboratory
0
Guided learning
0
Autonomous learning
10
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 assigments must be done individually. 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 aditional week to hand out the written resolution. You can expect to get two or three problems along the course.
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, the teacher will assign programming exercises to each student. In the assigments, the student must design and encode programs in C++ that solve the proposed problems, for instance, to Implement two algorithms that solve the same problem and to carry out a computational experiment that allow to compare the performance of the two algorithms, and at the same time, to compare these performances with the predictions of the theoretical analysis. Each student will have to solve several programming exercises individually
and another teaming with another student (teams of two people).
This last programming assignment will be use 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 scores of the resolution of algorithmic problems (E), the programming assignments (P), the written final exam (F) and the autonomous learning project (A) according to the formula
NF = 0.6 F + 0.1 E + 0.1 P + 0.2 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 A 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
Probability and computing: randomized algorithms and probabilistic analysis -
Mitzenmacher, M.; Upfal, E, Cambridge University Press ,
2005.
ISBN: 0521835402 http://cataleg.upc.edu/record=b1264917~S1*cat
Networks, crowds, and markets: reasoning about a highly connected world -
Easley, D.; Kleinberg, J, Cambridge University Press ,
2010.
ISBN: 9780521195331 http://cataleg.upc.edu/record=b1376401~S1*cat
- 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