Algorismes, Estructures de Dades i Bases de Dades

Esteu aquí

Crèdits
6
Tipus
Optativa
Requisits
Aquesta assignatura no té requisits, però té capacitats prèvies
Departament
CS;ESSI
This is a reinforcement course that covers basic concepts on algorithms, data structures and databases. This is an intensive course and, therefore, it is scheduled for 10 weeks. The first 5 weeks we will have double workload (with 8 hours per week) and then we will get back to the usual workload from week 6 to 10 with 4 hours per week.
The objective is to help you get the basic knowledge required by the other courses from the very beginning and specially during the weeks the semester has a lighter workload. Thus, the last 5 weeks of the semester there are no lectures and you can use them to focus on the other semester courses.

Professors

Responsable

  • Jordi Delgado Pin ( )
  • Oscar Romero Moral ( )

Altres

  • Alberto Abello Gamazo ( )

Hores setmanals

Teoria
2.7
Problemes
0
Laboratori
2.7
Aprenentatge dirigit
0
Aprenentatge autònom
9.6

Competències

Competències Tècniques Generals

Genèriques

  • CG1 - Capacitat per aplicar el mètode científic en l'estudi i anàlisi de fenòmens i sistemes en qualsevol àmbit de la Informàtica, així com en la concepció, disseny i implantació de solucions informàtiques innovadores i originals.
  • CG2 - Capacitat per a dirigir, planificar i supervisar equips multidisciplinaris.

Competències Transversals

Treball en equip

  • CTR3 - Ser capaç de treballar com a membre d'un equip, ja sigui com a un membre més, ja sigui realitzant tasques de direcció, amb la finalitat de contribuir a desenvolupar projectes d'una manera pragmàtica i amb sentit de la responsabilitat; assumir compromisos tenint en compte els recursos disponibles.

ús solvent dels recursos d'informació

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

Raonament

  • CTR6 - Capacitat de raonament crític, lògic i matemàtic. Capacitat de resoldre problemes en la seva àrea d'estudi. Capacitat d'abstracció: capacitat de crear i utilitzar models que reflecteixin situacions reals. Capacitat de dissenyar i realitzar experiments senzills, i analitzar-ne i interpretar-ne els resultats. Capacitat d'anàlisi, de síntesi i d'avaluació.

Bàsiques

  • 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.

Objectius

  1. Calculate the efficiency of iterative and recursive algorithms
    Competències relacionades: CG1, CB9, CTR4, CTR6,
    Subcompetences:
    • Compare the efficiency of different algorithms for solving the same problem and select the most appropriate one.
    • Compute the cost of an algorithm in the worst, best and average cases.
    • Understand the definitions of the Big-O, Omega and Theta asymptotic notations and their usefulness in characterising the efficiency of algorithms in time and space.
  2. Review of simple data structures and its implementation: lists, stacks, queues, trees.
    Competències relacionades: CG1, CB9, CTR4, CTR6,
  3. Understand, explain, design, analyse, compare and implement the main data structures that can be used to implement priority queues (trees, heaps).
    Competències relacionades: CG1, CB9, CTR4, CTR6,
  4. Understand, explain, design, analyse, compare and implement the main data structures that can be used to implement dictionaries (tables, sorted tables, lists, sorted lists, hash tables, binary search trees, AVL trees).
    Competències relacionades: CG1, CB9, CTR4, CTR6,
  5. Understand, explain, design, analyse, compare and implement algorithms that solve classic graph problems such as traversals, topological sorts, shortest paths, etc.
    Competències relacionades: CG1, CB9, CTR4, CTR6,
  6. Understand, explain, design, analyse, compare and implement algorithmic schemes using diverse techniques (divide and conquer, greedy, backtracking, etc)
    Competències relacionades: CG1, CB9, CTR4, CTR6,
  7. Identify computational limits: understand the implications of the question "P = NP?", understand the statement of Cook-Levin's Theorem, and recognise and identify several classic NP-complete problems.
    Competències relacionades: CG1, CB9, CTR4, CTR6,
  8. Describe what is a database and a database management system
    Competències relacionades: CG1, CB9, CTR4, CTR6,
    Subcompetences:
    • Distinguish the objectives of a database management system from a file system
    • Enumerate the objectives of a database management system
  9. Effectively use the standard Structured Query Language (SQL) to query relational databases
    Competències relacionades: CG1, CB9, CTR4, CTR6,
  10. Explain the relational data model, including its data structures, the relational algebra and integrity constraints
    Competències relacionades: CG1, CB9, CTR4, CTR6,
    Subcompetences:
    • Express any SQL query in terms of a relational algebra expression
  11. Identify the main objectives of a database management system query optimizer
    Competències relacionades: CG1, CB9, CTR4, CTR6,
    Subcompetences:
    • Evaluate the main pros and cons of the most popular data structures used by database management systems given a workload characterized in terms of database cardinality, size and the operations expected and their selectivity factor
    • Explain what is a cost model and how to automatically generate physical access plans
  12. Given a set of informational requirements, model the logic schema of a relational database
    Competències relacionades: CG1, CB9, CTR4, CTR6,
  13. Put in practice the course content on algorithmics, data structures and databases to solve real-life problems
    Competències relacionades: CG1, CG2, CB9, CTR3, CTR4, CTR6,

Continguts

  1. Basics of Analysis of Algorithms
    Cost in time and space. Worst case, best case and average case. Asymptotic notation. Analysis of the cost of iterative and recursive algorithms. Recurrences
  2. Simple Data Structures: Review
    Operations. Lists, Stacks, Queues, Trees
  3. Priority Queues
    Operations of priority queues. Implementations with heaps. Heapsort.
  4. Dictionaries
    Operations of dictionaries and ordered dictionaries. Basic implementations: tables and lists. Advanced implementations: hash tables, binary search trees, AVL trees
  5. Graphs
    Representations: adjacency matrices, adjacency lists and implicit representation. Depth-first search (DFS). Breadth-first search (BFS). Topological sort. Dijkstra's algorithm for shortest paths. Prim's algorithm for minimum spanning trees.
  6. Algorithmic schemes
    Divide and conquer, Greedy algorithms, Dynamic Programming, Exhaustive search, Backtracking.
  7. Notions of Intractability
    Basic introduction to P and NP classes. NP-completeness.
  8. Introduction to databases and database management systems
    Main concepts on databases and database management systems. Relational database management systems.
  9. SQL: Data-definition language and data-manipulation language
    Introduction to the SQL language
  10. The relational model
    Data structures and integrity constraints. Views.
  11. The relational algebra
    The relational algebra operators and how to build data pipes with them. Notion of semantic and syntactic optimization.
  12. Logical design of relational databases
    Normalization theory. Translating conceptual schemas into relational schemas.
  13. Notions of physical design and physical database optimization
    Notions of query optimizer, access plan and cost model

Activitats

Activitat Acte avaluatiu


Basics of Analysis of Algorithms

Cost in time and space. Worst case, best case and average case. Asymptotic notation. Analysis of the cost of iterative and recursive algorithms. Recurrences
Objectius: 1
Continguts:
Teoria
2h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

Review of simple data structures

Operations. Lists, Stacks, Queues, Trees
Objectius: 2
Continguts:
Teoria
1.5h
Problemes
0h
Laboratori
1.5h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Priority Queues

Operations of priority queues. Implementations with heaps. Heapsort.
Objectius: 3
Continguts:
Teoria
2h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Dictionaries

Operations of dictionaries and ordered dictionaries. Basic implementations: tables and lists. Advanced implementations: hash tables, binary search trees, AVL trees
Objectius: 4
Continguts:
Teoria
2h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Graphs

Representations: adjacency matrices, adjacency lists and implicit representation. Depth-first search (DFS). Breadth-first search (BFS). Topological sort. Dijkstra's algorithm for shortest paths. Prim's algorithm for minimum spanning trees.
Objectius: 5
Continguts:
Teoria
3h
Problemes
0h
Laboratori
3h
Aprenentatge dirigit
2h
Aprenentatge autònom
8h

Algorithmic schemes

Divide and conquer, Greedy algorithms, Dynamic Programming, Exhaustive search, Backtracking.
Objectius: 6
Continguts:
Teoria
5h
Problemes
0h
Laboratori
5h
Aprenentatge dirigit
0h
Aprenentatge autònom
11h

Notions of Intractability

Basic introduction to P and NP classes. NP-completeness.
Objectius: 7
Continguts:
Teoria
1h
Problemes
0h
Laboratori
1h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

First Partial Exam

This exam will assess the first 2/3 of the total content of the course
Objectius: 1 2 4 5 6 7 3
Setmana: 6
Tipus: examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Introduction to databases and database management systems

The student attends the lecture, takes notes and participates in the session exercises
Objectius: 8
Continguts:
Teoria
1h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
2h

SQL

The student attends the lecture, takes notes and participates in the session exercises
Objectius: 9
Continguts:
Teoria
1h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

The Relational Model

The student attends the lecture, takes notes and participates in the session exercises
Objectius: 10 12
Continguts:
Teoria
2h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
1h
Aprenentatge autònom
6h

Logical Design of Relational Databases

The student attends the lecture, takes notes and participates in the session exercises
Objectius: 10 12
Continguts:
Teoria
1h
Problemes
0h
Laboratori
2h
Aprenentatge dirigit
0h
Aprenentatge autònom
4h

Physical Optimization

The student attends the lecture, takes notes and participates in the session exercises
Objectius: 11
Continguts:
Teoria
4h
Problemes
0h
Laboratori
1h
Aprenentatge dirigit
0h
Aprenentatge autònom
8h

Second Partial Exam

Closed book exam on databases and database management systems
Objectius: 8 9 10 12 13 11
Setmana: 11
Tipus: examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h

Metodologia docent

During the master classes the lecturer provides material related to the topic and proposes exercises. During the labs the lecturer proposes material and exercises to be solved with the computer. For the algorithms and data structures part, the "Jutge" tool will be used. For the database part, the "Learn-SQL" tool will be used.

Due to the heterogeneous background of the students taking the course, and also due to the fact this is a reinforcement course on basic Computer Science concepts, the autonomous learning is extremely important in this course. The student will be provided with several exercise to be done at home (whenever possible, through "Jutge" or "Learn-SQL"). It is the student responsibility to adapt the autonomous workload to his / her background needs.

Mètode d'avaluació

Let P1 be the score of the first partial exam.
P2 the score of the second partial exam
EF the score of the final exam
Pr1 the score of the first practical work
Pr2 the score of the second practical work
Then,
NT = MAX(EF, P1*2/3 + P2*1/3)
NP = Pr1*2/3 + Pr2*1/3
So the final score will be 0.6*NT + 0.4*NP
Transversal competences will weight a 0% in the final score.

Bibliografia

Bàsica:

Complementaria:

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.

Addenda

Continguts

The syllabus does not change.

Metodologia docent

The course is scheduled to be given face-to-face. No changes.

Mètode d'avaluació

No changes.

Pla de contingència

In case a new lock-down is set, the course will be fully online. However, we will prioritize synchronous online sessions. Specifically: 1) Theory: we will provide materials (documents, videos, exercises) for the students and topic. The students should prepare this material on their own. Sessions to answer doubts will be scheduled (either by e-mail or, if needed, by videoconference). For those sessions that the lecturers estimate more difficulties, synchronous lectures by videoconference will be given. The intention is to record these sessions so that the students have access to them later. However, recording will only happen if UPC maintains the Google Meet recording option as in the previous semester (this is unclear when writing this addendum) or if the lectures are able to find a reasonable alternative. 2) Labs (and practical work): labs will be mainly asynchronous. During the first minutes of the labs, the lecturers will explain the objective of the lab and will remain in the session for 30-45' answering questions. Besides that, the students will work on the labs on their own. Sessions to answer doubts will be scheduled (either by e-mail or, if needed, by videoconference).