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
Teachers
Person in charge
Anna Queralt Calafat (
)
Maria Josefina Sierra Santibañez (
)
Others
Oscar Romero Moral (
)
Weekly hours
Theory
1
Problems
0
Laboratory
3
Guided learning
0
Autonomous learning
7.11
Competences
Transversal Competences
Information literacy
CT4 - Capacity for managing the acquisition, the structuring, analysis and visualization of data and information in the field of specialisation, and for critically assessing the results of this management.
Third language
CT5 - Achieving a level of spoken and written proficiency in a foreign language, preferably English, that meets the needs of the profession and the labour market.
Basic
CB6 - Ability to apply the acquired knowledge and capacity for solving problems in new or unknown environments within broader (or multidisciplinary) contexts related to their area of study.
CB9 - Possession of the learning skills that enable the students to continue studying in a way that will be mainly self-directed or autonomous.
Generic Technical Competences
Generic
CG1 - Identify and apply the most appropriate data management methods and processes to manage the data life cycle, considering both structured and unstructured data
Technical Competences
Especifics
CE1 - Develop efficient algorithms based on the knowledge and understanding of the computational complexity theory and considering the main data structures within the scope of data science
CE2 - Apply the fundamentals of data management and processing to a data science problem
Objectives
To analyse the cost of iterative and recursive algorithms
Related competences:
CT4,
CT5,
CE1,
To review some simple data structures: stacks, queues, lists, and trees
Related competences:
CT4,
CT5,
CE1,
To know, explain, design, analyse, compare and implement the main data structures and algorithms that can be used to implement priority queues
Related competences:
CT4,
CT5,
CE1,
To know, explain, design, analyse, compare and implement the main data structures and algorithms that can be used to implement dictionaries
Related competences:
CT4,
CT5,
CE1,
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
Related competences:
CT4,
CT5,
CE1,
To know, understand, explain, analyse and compare some algorithm design techniques: greedy, divide and conquer, and dynamic programming
Related competences:
CT4,
CT5,
CE1,
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
Related competences:
CT4,
CT5,
CE1,
Describe what is a database and a database management system
Related competences:
CT4,
CT5,
CE2,
Effectively use the standard Structured Query Language (SQL) to query relational databases
Related competences:
CT4,
CT5,
CE2,
Explain the relational data model, including its data structures, the relational algebra and integrity constraints
Related competences:
CT4,
CT5,
CE2,
Given a set of informational requirements, model the logic schema of a relational database
Related competences:
CT4,
CT5,
CE2,
Identify the main objectives of a database management system query optimizer
Related competences:
CT4,
CT5,
CE2,
Apply data structures, algorithms and database queries to solve a problem in a realistic situation
Related competences:
CT5,
CG1,
CE1,
CE2,
CB6,
CB9,
Contents
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 correctness and 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.
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
Design the logical schema of a database.
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.
Activities
ActivityEvaluation act
Basic concepts on Algorithms, Data Structures, and Databases
Motivation and main concepts on algorithmics, data structures, and database management systems. Objectives:128 Contents:
For students with a minor in Computer Science, this exam evaluates their knowledge on fundamental concepts of algorithms, data structures and databases. Objectives:394671258101112 Week:
8 Type:
theory exam
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h
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. Objectives:39467510111213 Contents:
For students with a minor in Computer Science, this exam evaluates their knowledge on fundamental concepts of algorithms, data structures and databases Objectives:394671258101112 Week:
14 Type:
theory exam
Theory
3h
Problems
0h
Laboratory
0h
Guided learning
0h
Autonomous learning
6h
Teaching methodology
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. Lectures focus on the main concepts and those that require some additional explanation to guarantee a proper understanding. Students will have a large bank of self-assessing exercises to practice their understanding on their own. During the course, they will have to solve some mandatory exercises to guarantee a smooth learning process. Additionally, in the face-to-face lectures, the lecturer will solve doubts, go through representative exercises to guarantee a solid understanding and discuss exercises (to be solved during the lecture) with the students.
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.
Evaluation methodology
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 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 = MAX (0.2*ADSEx + 0.4*ADSM + 0.4*ADSF, ADSF).
ADSDB (final course mark) = 0.5*BD + 0.5*ADS
2) If the student followed track 2 (see methodology) the mark is calculated as follows:
ADSDB (final course mark) = DS-EtE
Bibliography
Basic:
Introduction to algorithms -
Cormen, T.H. [et al.],
MIT Press, 2022. ISBN: 9780262046305
Computers and intractability: a guide to the theory of NP-Completeness -
Garey, M.R.; Johnson, D.S,
W.H. Freeman, 1979. ISBN: 0716710447 http://cataleg.upc.edu/record=b1008002~S1*cat
Understanding SQL and Java together: a guide to SQLJ, JDBC, and related technologies -
Melton, J.; Eisenberg, A, Morgan Kaufmann Publishers ,
2000.
ISBN: 1558605622 http://cataleg.upc.edu/record=b1173373~S1*cat
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.