Advanced Algorithmics

You are here

Home » Studies » Bachelor's degrees » Bachelor Degree in Informatics Engineering » Curriculum » Syllabus » 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
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

  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. 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.
  5. Approximation Algorithms
    Optimization Problems and Approximability.
    Algorithmic methods: Greedy algorithms, methods based on Linear Programming.
  6. Fixed Parameter Algorithms
    Parameterized problems: Vertex cover, Max Sat, Knapsack.
    Algorithmic Methods: Bounded-depth Search trees, Kernelization.
  7. Data Stream Algorithms
    Some basic problems.
    Computational models for data flows.
    Algorithmic Methods: Sampling, Sketches, techniques for streams of graphs.

Activities

Activity Evaluation act


Delivery of problems: Intractability


Objectives: 1 2 3
Week: 5 (Outside class hours)
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Delivery of problems: Solutions to Intractable problems (I)


Objectives: 1 2 4 5
Week: 8 (Outside class hours)
Type: assigment
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

Delivery of problems: Solutions to Intractable problems (II)


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

Midterm Exam 1


Objectives: 1 2 3 4 8
Week: 8
Type: problems exam
Theory
0h
Problems
3h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Midterm Exam 2

Written exam
Objectives: 5 7 6
Week: 14
Type: problems exam
Theory
0h
Problems
3h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

Final Exam

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

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
5h
Problems
1h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h

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
5h
Problems
1h
Laboratory
0h
Guided learning
0h
Autonomous learning
5h

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
2h
Laboratory
0h
Guided learning
0h
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
0h
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
6h
Problems
1h
Laboratory
0h
Guided learning
0h
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. 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.

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.