Advanced Algorithmics

Credits
6
Types
  • GRAU: Specialization complementary (Computing)
  • GCED: Elective
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

Weekly hours

Theory
2
Problems
2
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. 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.
    2. Random Algorithms
      Monte-Carlo Algorithms. Las Vegas Algorithms. Generation of random numbers. Factoritzation (Heurístic Pollard Rho). Criptography (RSA)
    3. 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.
    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: Graph streams, Sampling, Sketches.

    Activities

    Activity Evaluation act


    Midterm Exam 1


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

    Midterm Exam 2

    Written exam
    Objectives: 5 7 6
    Week: 14 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Final Exam

    Written exam.
    Objectives: 1 2 3 4 5 7 6 8
    Week: 15 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

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

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

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

    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
    3h
    Problems
    4h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    8h

    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
    4h
    Problems
    4h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    8h

    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 and that of the assignments/presentations (A); 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 grade A, and the grades for the partial exams P1 and P2 as follows:

    Continuous Grade= 0.2 A + 0.4 P1 + 0.4 P2

    The student may not take the final exam and, if so, 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.