Algorithms are present everywhere, further away than Computer Science. For example, basic notions used by biologists to express similarities between genes and genomes are algorithmic definitions. Even when economists analyze the feasibility of combinatorial auctions. These auctions are interpreted as search problems that can be shown to be computationally intractable, i.e. problems that can not be solved efficiently. The notion of computationally intractable problem and, in particular the notion of NP-completeness, have a fundamental role in the design of algorithms. Many problems in practice (optimization, artificial intelligence, combinatorics, logic, ...) are of this kind. Once a problem is classified as a computationally difficult one, we should be able to find a satisfactory solution. In this course we introduce techniques that allow us to deal with difficult problems: approximation algorithms (compute efficiently near optimal solutions to some optimization problems), fixed parameter algorithms (identify a parameter of problem so that the problem becomes tractable when this parameter is fixed). We also extend the set of random techniques discussed so far in previous courses.
Teachers
Person in charge
Maria del Carme Alvarez Faura (
)
Others
Maria Jose Serna Iglesias (
)
Weekly hours
Theory
3
Problems
1
Laboratory
0
Guided learning
0
Autonomous learning
6
Competences
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.
CCO2.6
- To design and implement graphic, virtual reality, augmented reality and video-games applications.
Objectives
To know the fundamental concepts of Computational Problem and Algorithm. To be able to analyze the computational resources like Time and Space, which are required by an algorithm.
Related competences:
CCO1.1,
To know how to classify the complexity of a computational problem. To be able to distinguish between tractable problems and intractable problems. Knowing the techniques of reducibility and completeness to analyze the computational difficulty of a problem.
Related competences:
CCO1.1,
G7.3,
To know some classical intractable problems and the classes that are identified by these problems: NP, PSPACE, EXP i NEXP.
Related competences:
CCO1.1,
G7.3,
To know Random Algorithms to solve intractable problems. In particular, to know two varieties of random algorithms: Monte Carlo algorithms which compute in polynomial time a solution that it may be not correct with low probability and Las Vegas algorithms which always compute a correct solution and guarantee polynomial time with high probability.
Related competences:
CCO1.1,
G7.3,
To know Approximation Algorithms to compute efficiently approximate solutions (solutions close to the optimum) for optimization intractable problems.
Knowing their limitations or problems that can not be approximated in polynomial time.
Related competences:
CCO2.5,
CCO1.1,
G7.3,
To know Fixed Parameter Algorithms that allow to solve in polynomial time certain restrictions of intractable problems. To know how to identify specific parameters of a problem so that when they are fixed then the problem can be solved efficiently.
Related competences:
CCO2.5,
G7.3,
To know Data Stream Algorithms to solve efficiently
problems where the inputs must be processed
by making one
or a small number of passes over it, using only a limited amount of working memory.
The streaming model applies to settings where the size of the input far exceeds the size
of the main memory available.
Related competences:
CCO2.5,
CCO2.6,
CCO1.1,
G7.3,
To know basic concepts of Game Theory: Games, strategies, costs, payoffs, selfish players. New solution concept: Nash equilibrium. Efficiency of solutions: Price of Stability and Price of Anarchy. Brief introduction to Network Formation Games.
Related competences:
CCO1.1,
Contents
Problems and Algorithms
Computational problems.
Complexity of algorithms: Time and Space.
Complexity of problems.
Tractable problems: Accessibility, Shortest paths.
Intractable problems: Traveling Salesman Problem, Knapsack.
Intractable Problems
Reducibility and Completeness.
NP-complete problems: Satisfiability, Subgraphs, Colorability, Tours, Partitions, Scheduling.
PSPACE, EXP, and NEXP problems: Quantified boolean formulae, games, tilling, equivalence of regular expressions.
Random Algorithms
Monte-Carlo Algorithms. Las Vegas Algorithms. Generation of random numbers. Factoritzation (Heurístic Pollard Rho). Criptography (RSA)
Algorithmics and Internet: Modelling Internet
Basic definitions: Game, strategy, cost and payoff, selfish players.
Nash Equilibrium, Social Cost, Price of Stability and Price of Anarchy
Introduction to Neetwork Formation Games. Understanding the behavior of Internet: A game equilibrium.
Approximation Algorithms
Optimization Problems and Approximability.
Algorithmic methods: Greedy algorithms, methods based on Linear Programming.
Data Stream Algorithms
Some basic problems.
Computational models for data flows.
Algorithmic Methods: Sampling, Sketches, techniques for streams of graphs.
Written exam. Objectives:12345768 Week:
15 (Outside class hours)
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
8h
Learning the topic "Problems and Algorithms"
Students attend the theory classes, try to understand this subject and solve problems, asking professor for help in the class of problems. Furthermore the students can also be asked to present one of the assigned problems to the blackboard.
Objectives:1 Contents:
Students attend the theory classes, try to understand this subject and solve problems, asking professor for help in the class of problems. Furthermore the students can also be asked to present one of the assigned problems to the blackboard.
Objectives:23 Contents:
Students attend the theory classes, try to understand this subject and solve problems, asking professor for help in the class of problems. Furthermore the students can also be asked to present one of the assigned problems to the blackboard.
Objectives:4 Contents:
Learning the topic "Algorithmics and Game Theory: Modelling Internet"
Students attend the theory classes, try to understand this subject and solve problems, asking professor for help in the class of problems. Furthermore the students can also be asked to present one of the assigned problems to the blackboard. Objectives:8 Contents:
Students attend the theory classes, try to understand this subject and solve problems, asking professor for help in the class of problems. Furthermore the students can also be asked to present one of the assigned problems to the blackboard.
Objectives:5 Contents:
Students attend the theory classes, try to understand this subject and solve problems, asking professor for help in the class of problems. Furthermore the students can also be asked to present one of the assigned problems to the blackboard.
Objectives:6 Contents:
Students attend the theory classes, try to understand this subject and solve problems, asking professor for help in the class of problems. Furthermore the students can also be asked to present one of the assigned problems to the blackboard. Objectives:7 Contents:
The theoretical contents of the course is taught in theory classes.
In the classes of problems students solve problems with the help of the professor and also present some of their solutions on the board.
Students have to deliver different written submissions presenting the solution of problems assigned by the professor. In some cases, it will be necessary to use methods that complement the ones seen in theory class and it will require some bibliographic research. In these cases the students will be
be asked to present solutions in public during the problem sessions.
Evaluation methodology
There are three types of evaluation activities: Delivery of problems, Presentations, and Final Exam.
Delivery of problems:
This part consist of solving lists of problems that have been assigned to each student as indicated in the plan. In the class of problems, the students can discuss their doubts together jointly with the professor, but it is considered as a personal and autonomous work that must be completed during their time of study. In general the solution will require to apply the acquired knowledge, to choose the appropriate method in each case and also to do some bibliographic research.
The students deliver their written solutions and present them in public if it is deemed appropriate (when the solutions extend the knowledge introduced in the current issue). The self-learning will be evaluated by this work.
The mark Pro of the delivery of problems is the average grade of all deliveries.
Exams:
There are two midterm exams and a final exam
in which it will be evaluated if the student has achieved the most general knowledge introduced throughout the course.
The mark of the continuous assessment of the subject is calculated from the mark of problems Pro and the marks of the partial exams P1 and P2 as follows:
Continuous = 0.2 Pro + 0.4 P1 + 0.4 P2
If Continuous >= 5, the student may not take the final exam and the Final Grade = Continuous.
If the student takes the final exam and obtains an ExF mark, then
Final Grade = max {ExF, (Continuous + ExF) / 2}
The evaluation of competence G7.3 will be carried out individually for each student based on public presentations and written solutions to the assigned problems.
The assessment of competence G7.3 does not affect the evaluation of the course.