Vai al contenuto principale
Coronavirus: aggiornamenti per la comunità universitaria / Coronavirus: updates for UniTo Community
Oggetto:
Oggetto:

Database and algorithms

Oggetto:

Database and algorithms

Oggetto:

Academic year 2017/2018

Course ID
MAT0040
Teaching staff
Prof. Rosa Meo
Dott. Rossano Schifanella
Year
1st year
Teaching period
Second semester
Type
D.M. 270 TAF C - Related or integrative
Credits/Recognition
12
Course disciplinary sector (SSD)
INF/01 - informatica
Delivery
Formal authority
Language
English
Attendance
Mandatory
Type of examination
Mixed
Prerequisites
Knowledge on programming.
Propedeutic for
Complex networks, Introduction to Data Mining
Oggetto:

Sommario del corso

Oggetto:

Course objectives

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

Databases

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. In the laboratory the students will be able to work with a practical database management system.

Algorithms

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

 

Oggetto:

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.

Oggetto:

Course delivery

This course consists in 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.

Oggetto:

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 (planned some days after the written part) the student will be asked to discuss the presented solution in the written part.

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

Algorithms

The final exams consists in 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.

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

Oggetto:

Support activities

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

Oggetto:

Program

Databases

Databases; database management systems; data models; database languages; the relational model and its languages;  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

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.

Suggested readings and bibliography

Oggetto:

Databases

Database Systems - Concepts, Languages and Architectures
Paolo Atzeni, Stefano Ceri, Stefano Paraboschi and Riccardo Torlone
McGraw-Hill
(http://dbbook.dia.uniroma3.it)

Algorithms

Suggested book:

Introduction to Algorithms. T Cormen, C Leiserson, R Rivest, C Stein



Oggetto:

Class schedule

Oggetto:
Last update: 02/06/2018 10:39
Non cliccare qui!