Advanced Algorithmics

Credits
6
Types
Specialization complementary (Computing)
Requirements
  • Prerequisite: A
Department
CS
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.4
Autonomous learning
5.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

  1. 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,
  2. 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,
  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,
  4. 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,
  5. 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,
  6. 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,
  7. 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,
  8. 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

  1. 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.
  2. 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.
  3. Random Algorithms
    Monte-Carlo Algorithms. Las Vegas Algorithms. Generation of random numbers. Factoritzation (Heurístic Pollard Rho). Criptography (RSA)
  4. Approximation Algorithms
    Optimization Problems and Approximability.
    Algorithmic methods: Greedy algorithms, methods based on Linear Programming.
  5. Fixed Parameter Algorithms
    Parameterized problems: Vertex cover, Max Sat, Knapsack.
    Algorithmic Methods: Bounded-depth Search trees, Kernelization.
  6. Data Stream Algorithms
    Some basic problems.
    Computational models for data flows.
    Algorithmic Methods: Sampling, Sketches, techniques for streams of graphs.
  7. 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.

Activities

Activity Evaluation act


Delivery of problems: Intractability


Objectives: 1 2 3
Week: 5
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Delivery of problems: Solutions to Intractable problems (I)


Objectives: 1 2 4 5
Week: 10
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Delivery of problems: Solutions to Intractable problems (II)


Objectives: 1 2 3 4 5 7 6 8
Week: 14
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
3h

Final Exam

Written exam.
Objectives: 1 2 3 4 5 7 6 8
Week: 15 (Outside class hours)
Type: final exam
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
3h
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:
Theory
3h
Problems
1h
Laboratory
0h
Guided learning
0h
Autonomous learning
4h

Learning the topic "Intractable Problems"

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: 2 3
Contents:
Theory
9h
Problems
3h
Laboratory
0h
Guided learning
1h
Autonomous learning
15h

Learning the topic "Random 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: 4
Contents:
Theory
6h
Problems
2h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

Learning the topic "Approximation 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: 5
Contents:
Theory
7h
Problems
3h
Laboratory
0h
Guided learning
0.5h
Autonomous learning
10h

Learning the topic "Fixed Parameter 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: 6
Contents:
Theory
7h
Problems
2h
Laboratory
0h
Guided learning
0.5h
Autonomous learning
9h

Learning the topic "Data Stream 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: 7
Contents:
Theory
7h
Problems
2h
Laboratory
0h
Guided learning
0.5h
Autonomous learning
9h

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:
Theory
6h
Problems
2h
Laboratory
0h
Guided learning
0.5h
Autonomous learning
9h

Teaching methodology

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. Depending on the difficulty of the problems, solutions may be presented in groups of 2 or 3 people. 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 (or each small group work) 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 (or groups) 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 and especially when the work is in group). The self-learning will be evaluated by this work.

The mark Pro of the delivery of problems is the average grade of all deliveries.

Presentations:
Each group or individually will be assigned sections of articles or books that will have to present in a limited time of maximum 20 minutes. The assigned material must allow to demonstrate in detail some of the results or properties announced in theory class.

The mark for the presentations Lec is the average of the mark for all presentations.


Exam:
There will be a final exam to evaluate whether the student knows the more important topics studied during all the course.

The final mark for the course is calculated from Pro, Lec, and ExF (the mark of the Exam) as follows:

Final Mark = 0.3 Pro + 0.2 Lec + 0.5 ExF

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.

Bibliography

Basic:

Complementary:

Previous capacities

Knowledge of algorithms and related concepts: efficiency of algorithms, asymptotic notation,
greedy algorithms, dynamic programming, ...

Basic knowledges of the theory of computation: automata, grammars, Turing machines, decidibilitat, complexity.

Critical capacity.

Mathematical maturity.

Addendum

Contents

No hi ha canvis.

Teaching methodology

La modificació important és que les classes de Teoria seran no presencials, síncrones i es faran via Meet. L'assignatura està organitzada en 2 hores/setmana de teoria, 1 hora/setmana teòrica pràctica i 1 hora/setmana de problemes. L'horari assignat a AA consta d'una franja de 2 hores de teoria (no presencial) i una franja presencial de 2 hores una de les quals és teòrica-pràctica (preparació i exposició de presentacions) i l'altra de problemes (preparació i exposició de problemes).

Evaluation methodology

No hi ha canvis.

Contingency plan

Si per emergència COVID haguéssim de fer la classe de problemes i la teòrica-pràctica també de manera no presencial, aleshores ho faríem semblant a la classe presencial, canviant la pissarra o projeccions per una presentació via Meet. Les solucions als problemes assignats s'hauran d'entregar via Pràctiques del Racó i durant la classe els estudiants les hauran de presentar i defensar via Meet (presentació del pdf entregat al Racó), explicant oralment les línies principals del seu argument. El professor farà els comentaris i correccions pertinents i prendrà nota de la valoració de cada presentació. Els exàmens es realitzaran de forma no presencial, amb entrega a través de Pràctiques del Racó.