- Oggetto:
- Oggetto:
DATABASE AND ALGORITHMS
- Oggetto:
DATABASE AND ALGORITHMS
- Oggetto:
Academic year 2015/2016
- 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
- Class Lecture
- 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 and Algorithms
The final exam will consist of a written test and an oral discussion on the two parts of the course in which 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 oral examination the student will be asked to proof to master the theory and the practical tools presented in class.
Students are required to pass the written test before to be admitted the practical part.
- 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
Days Time Classroom - Oggetto:
