This is a fundamental course that covers basic concepts on algorithms, data structures and databases. This course spans two different tracks: one for students who have a major in Computer Science and another track for the rest.
During the first weeks, the course is different for both tracks. For the former, it introduces students to CS-specific advanced topics for Data Science, while for the latter it requires the students to cover basic material on algorithms, data structures and databases in a guided, yet autonomous learning manner.
The last part of the course (corresponding to the last 5 weeks) is common and it is structured as project-based learning. A statement about an end-to-end Data Science project will be delivered and students will need to create the required software infrastructure, using adequate tools.
The objective is to help students get a rigorous and strong knowledge required by the following master courses (for students with a minor in CS) or investigate further CS-specific topics for Data Science (for students with a major in CS). Last, but not least, the course promotes adopting good habits when creating software projects for Data Science in the final project.
Professorat
Altres
Anna Queralt Calafat (
)
Maria Josefina Sierra Santibañez (
)
Oscar Romero Moral (
)
Hores setmanals
Teoria
1
Problemes
0
Laboratori
2.9
Aprenentatge dirigit
0
Aprenentatge autònom
6.85
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
To analyse the cost 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.
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.
Compute the cost of an algorithm in the worst, best and average cases.
To review some simple data structures: stacks, queues, lists, and trees
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
To know, explain, design, analyse, compare and implement the main data structures and algorithms that can be used to implement priority queues
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
To know, explain, design, analyse, compare and implement the main data structures and algorithms that can be used to implement dictionaries
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
To know, explain, design, analyse, compare and implement 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
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
To know, understand, explain, analyse and compare some algorithm design techniques: greedy, divide and conquer, and dynamic programming
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
To be aware of the limits of computation: to understand the definitions of the P and NP classes, the concept of Polynomial-Time reduction, the notion of NP-Completeness, and to know some classic NP-complete problems
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
Describe what is a database and a database management system
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
Subcompetences:
Enumerate the objectives of a database management system
Enumerate the objectives of a database management system
Distinguish the objectives of a database management system from a file system
Distinguish the objectives of a database management system from a file system
Effectively use the standard Structured Query Language (SQL) to query relational databases
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
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
Express any SQL query in terms of a relational algebra expression
Given a set of informational requirements, model the logic schema of a relational database
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
Identify the main objectives of a database management system query optimizer
Competències relacionades:
CG1,
CB9,
CTR4,
CTR6,
Subcompetences:
Explain what is a cost model and how to automatically generate physical access plans
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
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
Develop a quality realistic end-to-end system architecture for a data science project
Competències relacionades:
CG1,
CG2,
CB9,
CTR3,
CTR4,
CTR6,
Continguts
Basics of Analysis of Algorithms
Worst case, best case and average case cost analysis. Asymptotic order of growth notations: Big-O, Omega and Theta. Analysis of the cost of iterative and recursive algorithms.
Simple Data Structures: Review
Stacks, queues, lists and trees.
Priority Queues
Operations of priority queues. Implementations with heaps. Heapsort.
Dictionaries
Operations of dictionaries. Basic implementations: tables and lists. Advanced implementations: hash tables, binary search trees, and AVL trees.
Graphs
Representations: adjacency matrices, adjacency lists and implicit representations. Depth-first search (DFS). Breadth-first search (BFS). Topological sort. Algorithms for shortest paths. Algorithm for minimum spanning trees.
Algorithm design techniques
Greedy, divide and conquer, and dynamic programming.
Introduction to NP and Computational Intractability
Basic introduction to P and NP classes, Polynomial-Time reduction, and NP-completeness. Examples of classic NP-complete problems.
Introduction to databases and database management systems
Main concepts on databases and database management systems. Relational database management systems.
SQL: Data-definition language and data-manipulation language
Introduction to the SQL language
The relational model
Data structures and integrity constraints. Views.
The relational algebra
The relational algebra operators and how to build data pipes with them. Notion of semantic and syntactic optimization.
Logical design of relational databases
Normalization theory. Translating conceptual schemas into relational schemas.
Notions of physical design and physical database optimization
Notions of query optimizer, access plan and cost model
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
ActivitatActe avaluatiu
Basics of Analysis of Algorithms
To compare the efficiency of different algorithms for solving the same problem and select the most appropriate one. To compute the cost of an algorithm in the worst, best and average cases. To understand the definitions of the asymptotic order of growth notations Big-O, Omega and Theta, and their usefulness in characterising algorithm efficiency in time and space. Objectius:1 Continguts:
For students with a minor in Computer Science, this exams evaluates their knowledge on fundamental concepts of algorithms, data structures and databases Objectius:1245673 Setmana:
12 Tipus:
examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
6h
Introduction to databases and database management systems
The student attends the lecture, takes notes and participates in the session exercises Objectius:8 Continguts:
For students with a minor in Computer Science, this exams evaluates their knowledge on fundamental concepts of algorithms, data structures and databases Objectius:8910111312 Setmana:
17 Tipus:
examen de teoria
Teoria
2h
Problemes
0h
Laboratori
0h
Aprenentatge dirigit
0h
Aprenentatge autònom
5h
Data Science Advanced Topics project (DS-AT project)
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.
Students with a minor in Computer Science will investigate and further study the fundamental concepts introduced in the lecturing hours.
Teoria
0h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
40h
Data Science End-to-End Project (DS-EE)
All students 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.
Teoria
0h
Problemes
0h
Laboratori
4h
Aprenentatge dirigit
0h
Aprenentatge autònom
45h
Metodologia docent
During the first 10 weeks, the students are divided in 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 in algorithms, data structures and databases. First, additional material to read, study and understand is provided. Students will have a large bank of exercises to practice their understanding on their own. Then, in the face-to-face lectures, the lecturer will solve doubts and go through representative exercises to guarantee a solid understanding. Also, for the most complex concepts, some regular teaching sessions will be scheduled.
Students in track2 will undertake a research project related to advanced topics of algorithms, data structures and databases within the context of data science. Relevant and critical problems such as data integration, entity resolution and data quality will be proposed. The student will have access to a description of the problem, some seminal research papers and reference tools in this matter.
The last 5 weeks of the semester is common for all students regardless of the track they followed during the first 10 weeks. During these weeks the course project takes place. Students must create a end-to-end system architecture to ingest, store, process, learn models and deploy such system for a realistic project with realistic data.
This course has a strong self-learning component. Complementing it, the lecturers will provide additional material, advice hours and complementary lectures and labs to guarantee a solid comprehension.
Mètode d'avaluació
Let E1 be the score of the partial exam,
E2 the score of the final exam,
RPM the score of the DS-AT project and
CPM the score of the DS-EE project.
Then,
NE = MAX(E2, E1)
If the student followed track 1 (see methodology) then NT = NE
else if student followed track 2 (see methodology) then NT = RPM
The final mark will be 0.6*NT + 0.4*CPM
Transversal competences will weight a 0% in the final score.
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.