Laurea Magistrale (M.Sc.) in Stochastics and Data Science

Database and algorithms

Database and algorithms

Academic year 2018/2019

Sommario del corso

• Course objectives
• Results of learning outcomes
• Course delivery
• Learning assessment methods
• Support activities
• Program
• Suggested textbooks and readings
• Teaching tools

Course objectives

The objectives are formalized for each of the two parts of the course.

Databases

As regards the “Knowledge and understanding” goal, this course will teach the fundamentals of relational theory, SQL language and its relationships with relational algebra, design of data in relational databases by means of the conceptual and logical design of databases. The course will introduce the students to the basic notions of NoSQL databases, important for the new generation of databases and the management of big data.

As regards “Applying knowledge and understanding”, “Making judgements” and the “Learning skills” the course offers in the laboratory, some practical work sessions in which students apply the learnt concepts and solve exercises. This learning by practice allows students to make choices, find strategies to solve problems, recognize their own mistakes by following the logical reasoning after the interactions with the system. During the solution of the database design exercises, students learn to follow certain design strategies and make judgements about their suitability in different contexts. 
After their interaction with a real database management system (Mysql Workbench) students will learn new skills of assisted design of a database, design of new SQL queries for solving given requests, understanding of a given database schema and database content. Finally, students will learn to analyse a set of requirements about a real case problem and learn to be creative in the design of a new database, suitable to solve a given set of requirements.

In the laboratory, the students will learn to work with a practical database management system (Mysql Workbench).

As regards the “Communication skills”, students will be able to learn them during the interactions with other students working in a team for the solution of exercises (both in the laboratory sessions and in the database design classes). Students will be able to ask questions and explain and propose their own solutions.

Algorithms

As regards the “Knowledge and understanding” goal, in this course, students will learn several fundamental principles of algorithm design and how to implement some fundamental data structures (e.g., graphs, arrays, trees, hash tables).

As regards the goals of “Applying knowledge and understanding”, “Making judgements” and “Learning skills”, this course aims at providing a solid methodological background for the analysis of algorithms in terms of their correctness, complexity (in time and in space), and tractability. These are solid conceptual tools that will guide them during the choices of the correct algorithmic solutions for solving problems in real professional life.

Students will learn the skills to design and write a new algorithm (in a popular programming language for data science like Python) working on complex data structures. They will learn to recognise the contexts for the application of algorithms.

As regards the “Communication skills”, students will learn them during their work in a team with other students for the design, implementation of a practical project, assigned in Python and by the interaction with the teacher in these projects.

Results of learning outcomes

Databases

After the course, students will be able to design data for relational databases, formulate a query in SQL or relational algebra, interact with a real database management system and will have the basic notions of NoSQL databases.

Algorithms

After the course, students will be able to approach a problem through the design, analysis and implementation of appropriate algorithms and data structures.

Course delivery

This course consists of two parts: the former is on Databases and the latter is on Algorithms.

Databases

The course will consist of 32 hours of frontal lessons and 16 hours of practical assignments at the computer or at assigned exercises. Personal training on the assigned exercises on both the theory and practice modules is fundamental to successfully pass the final exam.

Algorithms

The course will consist of 32 hours of frontal lessons and 16 hours of practical assignments at the computer. Personal training on the assigned exercises on both the theory and practice modules is fundamental to successfully pass the final exam.

Learning assessment methods

Databases

The final exam will consist of a written test and a following oral discussion. In the written test the candidate will be asked to solve some data design problems, write in SQL a data retrieval request, present and discuss the practical assignments implemented during the course.

During the following, oral exam (which is optional and planned some days after the written part) the student will be asked to discuss the presented solution in the written part and will be asked to answer a question on the theoretical part of the course not included in the written test (Normalisation theory, transactions and concurrency control). This oral part will account for 2 scores only on the Database score.

Students are required to pass the written test before they are admitted to the oral part.

Algorithms

The final exams consist of an oral discussion of a project in which the students are asked to select a problem of interest, define a set of algorithmic solutions, compare them in terms of complexity and test their implementation within the framework of a real use case. Propaedeutic to the oral discussion is the submission of an essay that describes in details the projects main building blocks.

In the end, both the tests on the two parts of the course (Databases and Algorithms) must be satisfactory to allow the student to overcome the overall examination.

As regards the overall score, the two parts weigh equally in the final score, computed as the average of the scores of the two parts (Database and Algorithms): for the final score the average is rounded to the nearest integer.

Support activities

The laboratory will consist of assignments that will be solved by means of practical activities at the computer that will support the theoretical notions learnt during the course.

In addition, the practical laboratory sessions will support the students to learn the usage and the working of a real database management system (Mysql) and the assisted design of a database schema (Mysql Workbench).

Program

Databases

• Introduction to databases;
• database management systems;
• data models;
• database languages; 
• the relational model;  
• integrity constraints;
• relational algebra;
• SQL;
• Database design methodologies and models;
• the database design process;
• the Entity-Relationship model;  
• conceptual design;
• requirement collection and analysis;
• general data modelling criteria;
• design strategies;
• qualities of a conceptual schema;
• a general methodology for database design;
• CASE tools for database design;
• logical design;
• translation towards the relational model;
• Normalization theory for database design;
• redundancies and anomalies;
• functional dependencies;
• Boyce- Codd normal form;
• qualities of decompositions;
• third normal form;
• normalization and the design process
• hints on indexes
• transactions
• an overview of concurrency control
• basic notions of NoSQL databases (if time allows)
• Use of a real DBMS for database design and creation and queries with SQL (Mysql Workbench)

Algorithms

• Problems and algorithms: solvability, correctness, complexity.
• Termination and non-termination.
• Unsolvable problems: undecidability of the halting problem.
• Correctness of algorithms.
• Mathematical induction principles: simple induction, complete induction, structural induction.
• Analysis of algorithms.
• Complexity (in time and in space) of algorithms.
• Complexity of problems.
• Tractable vs. intractable problems and algorithms.
• Data structures,
• Abstract Data Types (ADT),
• structure invariants.
• Sequences, arrays, linked lists, stacks, queues, trees, dictionaries, hash tables.
• Graph representation and primitives.
• Sorting and selection.

Databases

Database Systems - Concepts, Languages and Architectures
Author: Paolo Atzeni, Stefano Ceri, Stefano Paraboschi and Riccardo Torlone
Publisher: McGraw-Hill
ISBN: 0077095006
Url: http:// http://dbbook.dia.uniroma3.it

Algorithms

Introduction to Algorithms
Author: T Cormen, C Leiserson, R Rivest, C SteinEdition: Third Edition
Publisher: MIT Press
ISBN: 9780262033848
Url: https://www.amazon.com/Introduction-Algorithms-Hardcover-2009-3rd-dp-B004D809WE/dp/B004D809WE/ref=mt_paperback?_encoding=UTF8&me=&qid=

Class schedule

• Teaching materials
• Exams and finals
• Go to Moodle
• Visit the forums