Algorithmics and Programming III

Credits
6
Types
Compulsory
Requirements
This subject has not requirements , but it has got previous capacities
Department
CS
In this subject we will study the main algorithmic schemes for solving complex computational problems. At the same time we will introduce the tools needed to implement these algorithms in a modern programming language.

Teachers

Person in charge

Others

Weekly hours

Theory
2
Problems
1
Laboratory
1
Guided learning
0
Autonomous learning
6

Competences

Technical Competences

Technical competencies

  • CE2 - To be able to program solutions to engineering problems: Design efficient algorithmic solutions to a given computational problem, implement them in the form of a robust, structured and maintainable program, and check the validity of the solution.
  • CE7 - Demonstrate knowledge and ability to apply the necessary tools for the storage, processing and access to data.

    • Transversal Competences

    Transversals

  • CT4 [Avaluable] - Teamwork. Be able to work as a member of an interdisciplinary team, either as a member or conducting management tasks, with the aim of contributing to develop projects with pragmatism and a sense of responsibility, taking commitments taking into account available resources.
  • CT5 - Solvent use of information resources. Manage the acquisition, structuring, analysis and visualization of data and information in the field of specialty and critically evaluate the results of such management.
  • CT6 - Autonomous Learning. Detect deficiencies in one's own knowledge and overcome them through critical reflection and the choice of the best action to extend this knowledge.
  • CT7 - Third language. Know a third language, preferably English, with an adequate oral and written level and in line with the needs of graduates.

    • Basic

  • CB5 - That the students have developed those learning skills necessary to undertake later studies with a high degree of autonomy

    • Generic Technical Competences

    Generic

  • CG1 - To design computer systems that integrate data of provenances and very diverse forms, create with them mathematical models, reason on these models and act accordingly, learning from experience.
  • CG2 - Choose and apply the most appropriate methods and techniques to a problem defined by data that represents a challenge for its volume, speed, variety or heterogeneity, including computer, mathematical, statistical and signal processing methods.
  • CG5 - To be able to draw on fundamental knowledge and sound work methodologies acquired during the studies to adapt to the new technological scenarios of the future.

    • Objectives

    1. Be aware of the limits of computation: to undertand the implications of the question "P=NP?", understand the statement of Cook-Levin's Theorem, recognize and identify several classic NP-complete problems.
      Related competences: CG5,
    2. To know, explain, design, analyze, compare and implement exhaustive search algorithms using the backtracking technique.
      Related competences: CE2, CB5,
    3. To learn the dynamic programming scheme, identify when it can be applied and how, and be familiar with some fundamental dynamic programming algorithms.
      Related competences: CE2,
    4. To learn the scheme of greedy algorithms, identify when it can be applied and how, learn the most usual techniques for proving their correctness and be familiar with some fundamental greedy algorithms.
      Related competences: CE2,
    5. To complete and modify implementations of several algorithms for solving problems of average difficulty in the Python programming language.
      Related competences: CE2, CT6,
    6. Identify and propose solutions to possible problems of efficiency in programs written in the Python programming language.
      Related competences: CE2, CT6,
    7. To develop projects of average size as as member of a team, learning how to divide a project into smaller parts, to distribute them amongst its members and act with responsability in a coordinated way for the successful accomplishment of the assigned tasks.
      Related competences: CE2, CT4, CT5, CT6, CT7, CG1, CG2,
    8. To learn algorithms based on local search for solving untractable problems efficiently. To learn a variety of metaheuristics of different nature and to be able to identify when and how they can be applied on concrete computationally hard problems.
      Related competences: CE2,
    9. To learn the foundations of finite automata and regular expressions to be able to use them in practice (search of patters in texts, etc.)
      Related competences: CE7,

    Contents

    1. Tractability: classes of problems P and NP
      Classes P and NP, Cook-Levin's Theorem, reductions, NP-completeness.
    2. Exhaustive search
      Theoretical foundations: space of solutions, partial solutions, pruning. Examples: subsets, permutations, travelling salesman, subset sum.
    3. Dynamic programming
      Top-down scheme (memoization). Bottom-up scheme (tabulation). Examples: Fibonacci, binomial numbers, knapsack, matrix sequence multiplication.
    4. Greedy algorithms
      Theoretical foundations: general scheme of greedy algorithms. Examples: task scheduling, etc.
    5. Metaheuristics
      Local search. Simulated Annealing, Tabu Search, GRASP, genetic algorithms.
    6. Finite automata and regular expressions
      Alphabets, words, languages. Deterministic finite automata, non-deterministic finite automata, finite automata with lambda-transitions, equivalence between automata models, minimization of automata.
      Regular expressions, equivalence with automata. Operations.

    Activities

    Activity Evaluation act


    Tractability


    Objectives: 1
    Contents:
    Theory
    6h
    Problems
    4h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    8h

    Exhaustive Search


    Objectives: 2 5 6
    Contents:
    Theory
    4h
    Problems
    0h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    8h

    Dynamic Programming


    Objectives: 3 5 6
    Contents:
    Theory
    4h
    Problems
    0h
    Laboratory
    4h
    Guided learning
    0h
    Autonomous learning
    8h

    Greedy Algorithms


    Objectives: 4 5 6
    Contents:
    Theory
    4h
    Problems
    2h
    Laboratory
    2h
    Guided learning
    0h
    Autonomous learning
    8h

    Metaheuristics


    Objectives: 8 5
    Contents:
    Theory
    4h
    Problems
    0h
    Laboratory
    6h
    Guided learning
    0h
    Autonomous learning
    8h

    Finite automata and regular expressions


    Objectives: 9
    Contents:
    Theory
    4h
    Problems
    4h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    8h

    Consolidation


    Objectives: 2 1 3 4 9 8
    Contents:
    Theory
    4h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    8h

    Mid term exam


    Objectives: 2 1 3
    Week: 8
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Project - Exhaustive Search


    Objectives: 2 5 6 7
    Week: 8 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Project - Greedy Algorithms


    Objectives: 4 5 6 7
    Week: 12 (Outside class hours)
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Lab exam


    Objectives: 2 3 4 9 8 5 6
    Week: 13
    Theory
    0h
    Problems
    0h
    Laboratory
    0h
    Guided learning
    0h
    Autonomous learning
    0h

    Project - Metaheuristics


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

    Final exam


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

    Teaching methodology

    The syllabus is explained in a practical way, through the presentation of many examples.

    Theory lectures introduce all of the required concepts and techniques, which are put into practice in the problem and lab lectures by means of a collection of problems and exercices in an automatic judge.

    The two hours of theory classes are taught weekly. The two hours of lab classes are taught every other week. The two hours of problem classes are taught every other week.

    The project integrates the contents and competences of all the course.

    Evaluation methodology

    NPar = grade mid term exam
    NFT = grade final theory exam
    NFL = grade final lab exam
    NPro = grade project

    FINAL GRADE = max( 30%Npar + 30%NFT + 20%NFL + 20% NPro, 60%NFT + 20%NFL + 20% NPro)

    The grade of the reevaluation exam, if there is any and is higher, replaces the grade of the theory final exam (NFT). The grades of mid term, project and lab (NPar, NPro, NFL) are preserved.

    Bibliography

    Basic

    Complementary

    Web links

    Previous capacities

    - Familiarity with the basic techniques of programming: iterations, alternatives, recursive functions, parameter passing, classes, objects, methods, ...

    - Knowledge of basic algorithmic concepts: efficiency of algorithms, asymptotic notation, graphs, graph traversal, data structures (lists, search trees, hash, heaps, ...)

    - Basic knowledge of discrete mathematics, linear algebra and calculus

    - Basic knowledge of probability theory and statistics