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.
Learning Objectives
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.
Prerequisites
none
Teaching Methods
CFU: 12
Total hours of the course:
300
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.
Further information
Frequency of lessons and exercises: Recommended
Tools to support teaching UniFi E-Learning: http://el.unifi.it
Office hours:
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
Appointment.
Department of Mathematics and Computer Science
Viale Morgagni, 65
50134 - Florence (FI)
E-Mail: antonio.bernini @ unifi.it
Type of Assessment
The exam consists of a written test (on simulation exercises of algorithms and data structures) and an oral test with questioning about the whole program and the discussion of a project to be developed in small groups (2-3 people).
The written test will evaluate the understanding of the functioning of the data structures and the 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. To access the oral exam it is necessary to pass the written exam.
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 arithmetic average of the mark of the oral and written 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.
The evaluation of the project affects 10% of the final evaluation
Course program
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.