C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e Strutture Dati, McGraw-Hill, 2008.
C. Demetrescu, U. Ferraro Petrillo, I. Finocchi, G.F. Italiano, Progetto di algoritmi e strutture dati in Java, McGraw-Hill, 2007.
Knowledge acquired - The student acquires knowledges about fundamental data structures (linear lists, trees and graphs), searching algorithms in internal memory, sorting algorithms and basic algorithms on graphs.
Competence acquired - The student acquires the competences to understand the design problems and algorithms evaluation, with particular reference to non- numeric algorithms. In particular, he will be able to analyse a problem, detect and/or design the resolving algorithms that are more appropriate to the problem and its applicative context, estimate the computational cost of the proposed solution; implement the solution in a correct and efficient way.
Skills acquired (at the end of the course) - The student is able to analyze a problem and determine the abstract data structures and the algorithm that best fits the context of the problem.
Total hours of the course:
Hours reserved to private study and other indivual formative activities: 192
Number of hours for classroom activities: 80
Number of hours for laboratory activities (laboratory classes): 24
Number of hours per course tests: 4
The course is organized in lectures, laboratory lessons and online activities.
Frequency of lessons and exercises: Recommended
Tools to support teaching UniFi E-Learning: http://el.unifi.it
Prof. M. Cecilia Verri
Prior appointment via e-mail
Department of Statistics, Computer Science, Applications
Viale Morgagni, 65
50134 - Florence (FI)
Tel: 055 2751513
E-Mail: mariacecilia.verri @ unifi.it
Prof. A. Bernini
Department of Mathematics and Computer Science
Viale Morgagni, 65
50134 - Florence (FI)
E-Mail: antonio.bernini @ unifi.it
Type of Assessment
Due to the health emergency, it was necessary to change the way the exams were conducted.
Therefore in the exam sessions of the 2019/20 academic year, the exam will consist of an oral proof with questions on the whole program, exercises to be carried out and discussion of a project that can be developed in small groups (2-3 people). Those who have passed the first intermediate test will not be asked to carry out exercises on the topics of the first part of the program.
The performance of the exercises will serve to evaluate the understanding of the functioning of the data structures and algorithms seen in class, the ability to analyze the complexity of simple structures and algorithms, the ability to apply the knowledge acquired to solve new problems.
The oral test will assess the knowledge of the topics presented, the acquisition of the technical language appropriate to the context, the ability to relate different topics of the program to each other.
The mark given in the oral test affects 90% of the final mark.
The project must be carried out in Java and the topic will be assigned after 70% of the laboratory exercises have been carried out. With regard to the development of the project, the strategies used to solve and carry out the project from the algorithmic point of view and the data structures used will be evaluated. During the discussion, students must demonstrate awareness of the choices made and the strategies put into practice.
Project evaluation affects the final evaluation by 10%
Introduction to Algorithms
Analysis of algorithms: basic operation and problem size, big O notation, complexity in the worst case and average case, the complexity in time and space, the fundamental relationships of recurrence.
Elementary data structures internal: arrays, linked lists, complexity of basic operations.
Abstract data structures: stacks, queues, priority queues, trees.
Search algorithms: binary search, binary search trees, AVL trees and 2-3, and digital trie search, random search.
Sorting algorithms: elementary algorithms, quicksort, mergesort, Heap sort, selection algorithms
Graphs: Representation of graphs, graph traversal.
Weighted graphs: Minimum spanning tree.