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 for topics other exercises (laboratory and field): 0
Number of hours for seminars to: 0
Number of hours related to work experience: 0
Number of hours per course tests: 4
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 algorithms and data structures simulation exercises, an oral examination on the whole program, and a project to be developed in small groups (2-3 people).
The project must be done in Java and the topic will be assigned after the holding of 70% of the laboratory exercises.
You can get an exemption from the written test surpassing the two interim tests that take place during the course.
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, algorithms visit.
Weighted graphs: Minimum spanning tree.