Algorismes, Estructures de Dades i Bases de Dades

Crèdits
6
Tipus
Obligatòria
Requisits
Aquesta assignatura no té requisits , però té capacitats prèvies
Departament
CS;ESSI
Web
https://learnsql.fib.upc.es/moodle/
This is a fundamental course that covers basic concepts on algorithms, data structures and databases. Even if the objectives of the course are common, this course spans two different tracks: one for students who have a major in Computer Science and another track for the rest.

The methodology is different for both tracks. For the former, it is a project-oriented course focusing on dataOps / MLOps, while for the latter it covers basic material on algorithms, data structures and databases in a guided, yet autonomous learning manner that will allow them to develop complex data systems.

Professorat

Responsable

Altres

Hores setmanals

Teoria
1
Problemes
0
Laboratori
3
Aprenentatge dirigit
0
Aprenentatge autònom
7.11

Competències

Competències Transversals

Ús solvent dels recursos d'informació

  • CT4 - Gestionar l'adquisició, l'estructuració, l'anàlisi i la visualització de dades i informació de l'àmbit d'especialitat, i valorar de forma crítica els resultats d'aquesta gestió.

    • Tercera llengua

  • CT5 - Conèixer una tercera llengua, preferentment l'anglès, amb un nivell adequat oral i escrit i en consonància amb les necessitats que tindran els titulats i titulades.

    • Bàsiques

  • CB6 - Que els estudiants sàpiguen aplicar els coneixements adquirits y la seva capacitat de resolució de problemes en entorns nous o poc coneguts dins de contexts més amplis (o multidisciplinaris) relacionats amb la seva àrea d'estudi.
  • CB9 - Que els estudiants posseeixin les habilitats d'aprenentatge que els permetin continuar estudiant d'una manera que haurà de ser en gran mesura autodirigida o autònoma..

    • Competències Tècniques Generals

    Genèriques

  • CG1 - Identificar i aplicar els mètodes i processos de gestió de dades més adequats per gestionar el cicle de vida de les dades, incloent-hi dades estructurades i no estructurades

    • Competències Tècniques

    Específiques

  • CE1 - Desenvolupar algoritmes eficients fonamentats en el coneixement i comprensió de la teoria de la complexitat computacional i les principals estructures de dades, dins de l'àmbit de ciència de dades
  • CE2 - Aplicar els fonaments de la gestió i processament de dades en un problema de ciència de dades

    • Objectius

    1. To specify a computational problem and justify the correctness and termination of an iterative or recursive algorithm that solves this problem.
      Competències relacionades: CT4, CT5, CE1,
    2. To carry out asymptotic analyses of the worst case running time of iterative and recursive algorithms.
      Competències relacionades: CT4, CT5, CE1,
    3. To review some simple data structures: stacks, queues, lists, and trees
      Competències relacionades: CT4, CT5, CE1,
    4. To know what a priority queue is, be able to use it to solve
      computational problems, and understand and analyse the main data
      structures and algorithms that are used to implement it.
      Competències relacionades: CT4, CT5, CE1,
    5. To know what ordered and unordered dictionaries are, be able to
      use them to solve computational problems, and understand and analyse
      the main data structures and algorithms that are used to implement
      them.
      Competències relacionades: CT4, CT5, CE1,
    6. To know the main data structures and algorithms that can be used
      to represent graphs and solve classic graph problems such as traversals,
      topological ordering and shortest paths, analyse their asymptotic
      running time and be able to use them to solve computational problems.
      Competències relacionades: CT4, CT5, CE1,
    7. To know what a decision problem is, the definitions of the
      P and NP classes of problems, what a polynomial-time reduction is
      and the associated notion of NP-completeness.
      Competències relacionades: CT4, CT5, CE1,
    8. Describe what is a database and a database management system
      Competències relacionades: CT4, CT5, CE2,
    9. Effectively use the standard Structured Query Language (SQL) to query relational databases
      Competències relacionades: CT4, CT5, CE2,
    10. Explain the relational data model, including its data structures, the relational algebra and integrity constraints
      Competències relacionades: CT4, CT5, CE2,
    11. Given a set of informational requirements, model the logic schema of a relational database
      Competències relacionades: CT4, CT5, CE2,
    12. Identify the main objectives of a database management system query optimizer
      Competències relacionades: CT4, CT5, CE2,
    13. Apply data structures, algorithms and database queries to solve a problem in a realistic situation
      Competències relacionades: CT5, CG1, CE1, CE2, CB6, CB9,

    Continguts

    1. Specification and Analysis of Algorithms
      Justification of correctness and termination of iterative and recursive
      algorithms.
    2. Asymptotic Analysis
      Asymptotic analysis: Order of growth, Big-O, Omega and Theta notations, asymptotic analysis of iterative algorithms, introduction to the asymptotic analysis of recursive algorithms (recurrences and the master method).
    3. Review of Object Oriented Programming
      Review of Fundamental Concepts of Object Oriented Programming.
    4. Basic Data Structures
      Basic Data Structures: stack, queue, linked-list and tree.
      Abstract Data Types, examples of use, and implementations.
    5. Priority Queue
      Priority Queue: ADT (operations) and examples of use.
      Implementation with heaps and asymptotic analysis. Heapsort algorithm.
    6. Ordered Dictionary
      Ordered Dictionary: ADT (operations) and examples of use. Implementation with binary search trees and AVL trees, and asymptotic analysis.
    7. Unordered Dictionary
      Unordered Dictionary: ADT (operations) and examples of use. Implementation with hash tables and asymptotic analysis.
    8. Graph
      Graph: Adjacency list and adjacency matrix representation. Traversal algorithms: depth-first search (DFS) and breadth-first search (BFS). Topological sort, shortest paths, and minimum spanning tree algorithms.
    9. Introduction to Complexity and Intractability
      Decision problems. P and NP classes of problems. Polynomial-time reduction and NP-completeness.
    10. Introduction to databases and database management systems
      Main concepts on databases and database management systems. Relational database management systems.
    11. SQL: Data-definition language and data-manipulation language
      Introduction to the SQL language.
    12. The relational model
      Data structures and integrity constraints.
    13. The relational algebra
      The relational algebra operators and how to build data pipes with them. Notion of semantic and syntactic optimization.
    14. Logical design of relational databases
      Design the logical schema of a database.
    15. Notions of physical design and physical database optimization
      Notions of query optimizer, access plan and cost model.
    16. Data Science-related advanced topics
      Students with a major in Computer Science will investigate on advanced topics specific for data science projects. For example, data
      quality, entity resolution, data integration, etc.

    Activitats

    Activitat Acte avaluatiu


    Basic concepts on Algorithms, Data Structures, and Databases

    Motivation and main concepts on algorithmics, data structures, and database management systems.
    Objectius: 8 1
    Continguts:
    Teoria
    7.5h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Partial Exam

    For students with a minor in Computer Science, this exam evaluates their knowledge on fundamental concepts of algorithms, data structures and databases.
    Objectius: 4 9 2 3 8 10 11 12 1
    Setmana: 8
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Computer Science for Data Science

    Students in the minor track will put in practice all the contents of the course by solving exercises related to algorithms, data structures, and databases. Students in the major track will undertake a project spanning all main phases of a data science. As result, they are asked to develop a quality realistic end-to-end system architecture for a data science project.
    Objectius: 4 9 5 7 2 3 6 10 11 12 13 1
    Continguts:
    Teoria
    0h
    Problemes
    0h
    Laboratori
    40.5h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    84h

    Final Exam

    For students with a minor in Computer Science, this exam evaluates their knowledge on fundamental concepts of algorithms, data structures and databases
    Objectius: 4 9 5 7 2 3 6 8 10 11 12 1
    Setmana: 14
    Teoria
    0h
    Problemes
    0h
    Laboratori
    0h
    Aprenentatge dirigit
    0h
    Aprenentatge autònom
    0h

    Metodologia docent

    The students are divided into two tracks: one for students with a minor in computer science (track 1) and another one for students with a major in computer science (track 2).

    Students in track 1 will study fundamental concepts on algorithms, data structures and databases.

    The Databases part for track 1 students is organized in theory sessions where the main concepts on relational databases, SQL, Relational Algebra and optimizations are presented. Examples and exercises will be introduced to practice and discuss alternative solutions during the class. Additional material to facilitate understanding theoretical concepts will be provided.
    Between sessions, students will have to solve some mandatory exercises to guarantee a smooth learning process. These exercises are individual and correspond to the DBEx part of the final grade in the evaluation.

    The Algorithms and Data Structures part for track 1 consists of theory, problems and programming sessions. During the 'theory sessions' the main concepts, data structures, algorithms and results will be presented and illustrated with examples. Additional material to read and problems to facilitate understanding theoretical concepts will be provided.
    Exercises on theoretical aspects of the course contents, such as justifying correctness and temination, asymptotic analysis of worst case running time, application of data structure operations or algorithms to particular problem instances, or demonstration of results on data structures and algorithms will be proposed. These exercises will be solved in groups of two or three students during the 'problems sessions', to promote discussion and team work. The lecturer will answer questions and suggest reading course material relevant to the problems. Assessment of written solutions submitted by each group corresponds to the ADSEx grade in the evaluation.
    Programming problems requiring the implementation and use of the main data structures presented in the course in Python will be proposed. Students should solve these problems individually during the 'programming sessions' and afterwards as homework. Assessment of programming problems corresponds to the ADSPr grade in the evaluation. and it will be carried out through short meetings requiring demonstration of some of the solutions submitted, explanation, and slight modifications.

    Students in track 2 will carry out the DS-EtE project and, for them, this course is a project course. There, students must create an end-to-end system architecture to ingest, store, process, learn models and deploy such system for a realistic project with realistic data. The students must develop good practices developing such architecture (what nowadays is known as DataOps / MLOps).

    This course has a strong self-learning component and shares the same objectives in both tracks. The lecturers will supervise the students progress during the semester to guarantee a proper progress.

    Mètode d'avaluació

    Let DBM = Databases midterm exam grade,
    DBF = Databases final exam grade,
    DBEx = Database exercises to be solved during the course,
    ADSM = Algorithms and Data Structures midterm exam grade,
    ADSF = Algorithms and Data Structures final exam grade and
    ADSEx = Algorithms and Data Structures exercises to be solved in groups during the course,
    ADSPr = Programming problems to be solved individually during the course,
    DS-EtE = DS-EtE project grade

    Then,

    1) If the student followed track 1 (see methodology) the mark is calculated as follows:
    BD = MAX (0.2*DBEx + 0.8*DBM, DBF),
    ADS = ADSPr*0.3 + ADSEx*0.1 + MAX(0.2*ADSM + 0.4*ADSF, 0.6*ADSF)


    ADSDB (final course mark) = 0.4*BD + 0.6*ADS

    2) If the student followed track 2 (see methodology) the mark is calculated as follows:

    ADSDB (final course mark) = DS-EtE

    Bibliografia

    Bàsic

    Complementari

    Web links

    Capacitats prèvies

    This course assumes basic competences in algorithms, data structures and databases. The course is structured to cope with different backgrounds and learning needs but basic knowledge on Computer Science principles is assumed: notions of computer architecture, basic programming constructs and data structures.