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
Web
https://www.cs.upc.edu/~mjserna/docencia/grauAA/AA-GEI.html
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 Jose Serna Iglesias ( )

Others

  • Maria del Carme Alvarez Faura ( )

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: G7.3, CCO1.1,
  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: G7.3, CCO1.1, CCO2.5,
  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: G7.3, CCO1.1, CCO2.5, CCO2.6,
  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. Dynamic programming and treewidth
  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


Written deliverable and/or oral presentation

Once or twice during the course, students (in groups) will have to solve problems and/or study algorithms related to topics presented in class. The problems will have to be submitted in writing and the new algorithms will have to be presented in class. This is considered a personal and autonomous work that must be completed during their study hours. This is the work in which the autonomous learning will be assessed.
Objectives: 1 2 3 4 5 7 6 8
Week: 10 (Outside class hours)
Theory
0h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
11h

Midterm Exam 1


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

Midterm Exam 2

Written exam
Objectives: 5 7 6
Week: 14 (Outside class hours)
Theory
0h
Problems
2h
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)
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
2h
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
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
7h
Problems
2h
Laboratory
0h
Guided learning
0h
Autonomous learning
10h

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
3h
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
10h

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
5h

Teaching methodology

The theoretical content of the course is taught in theory classes.

In problem's classes, the solutions proposed by the students to exercises will be discussed. These exercises will be set by the teacher in advance (more complex statements, with which the student has been able to work for a week, autonomously) or short exercises set during the same class to be worked on in teams of two to four students or individually. Students may be required to present their solutions to the rest of their classmates.

Students will have to make several presentations/deliveries of the solution to problems or algorithms assigned by the teacher. In some cases, finding the solution will require using methods that complement those seen in theory classes and will require doing a small bibliographic search. In these cases, the solutions will be asked to be presented publicly.

Evaluation methodology

The final grade is calculated from the grade for solving algorithmic problems in problem's class (A); the grade associated with the assignments/presentations (E); the grade for the written tests: partial (P1 and P2) and the final exam (F).

The grade for the continuous assessment of the subject is calculated from the grades A, E and the grades for the partial exams P1 and P2 as follows:

Continuous Grade= 0.2 ( 0.3 A + 0.7 E) + 0.4 P1 + 0.4 P2

If the Continuous Grade >= 5, the student may not take the final exam and the Final Grade = Continuous Grade.

If the student takes the final exam and obtains a grade of ExF, then

Final Grade = max { F, (Continuous Grade + F)/2 }

The assessment of the G7.3 competency is carried out by the teacher individually for each student based on the public and written presentations of the assigned topics.

The assessment of the competencies does not affect the assessment of the subject.

Bibliography

Basic:

Complementary:

Previous capacities

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

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

Critical capacity.

Mathematical maturity.