Algorithmics and Programming III

You are here

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

  • Enric Rodriguez Carbonell ( )

Others

  • Albert Oliveras Llunell ( )

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 C++ programming language.
    Related competences: CE2, CT6,
  6. Identify and propose solutions to possible problems of efficiency in programs written in the C++ 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
3h
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
9h

Project - Greedy Algorithms


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

Lab exam


Objectives: 2 3 4 9 8 5 6
Week: 13
Theory
0h
Problems
0h
Laboratory
3h
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
10h

Final exam


Objectives: 2 1 3 4 9 8
Week: 15 (Outside class hours)
Theory
3h
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