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), search 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 to 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 (including the time spent in attending lectures, seminars, private study, examinations, etc...): 300
Hours reserved to private study and other indivual formative activities: 192
Frequency of lectures, practice and lab: Recommended
Teaching Tools UniFi E-Learning: http://e-l.unifi.it
Office Hours:
Prof. M.C. Verri
Wednesdays, from 10.00 to 11.00 a.m., or by appointment via e-mail.
Dipartimento di Sistemi e Informatica
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237439 Fax: 055 4796363 - 4237436
E-Mail: mariacecilia.verri@unifi.it
URL: http://www.dsi.unifi.it/~cecilia/
Prof. A. Bernini
By appointment.
Dipartimento di Sistemi e Informatica
Viale Morgagni, 65
50134 - Firenze (FI)
Tel: 055 4237460 Fax: 055 4796363 - 4237436
E-Mail: antonio.bernini@unifi.it
Type of Assessment
Written, Practical and Oral
Course program
Introduction to algorithms
Complexity analysis of algorithms: fundamental operation and problem dimension, big O notation, complexity in the worst and average case, complexity in time and space, fundamental relations of recurrence.
Internal elementary data structures: arrays, concatenated lists, complexity of main operations.
Abstract data structures: stacks, queues, priority queues, trees.
Search algorithms: binary search, binary search trees, AVL and 2-3 trees, Digital search and trie, Random search.
Sort algorithms: Elementary algorithms, Quicksort, Mergesort, Heap sort, selection algorithms.
Graphs: graphs representation, visit algorithms.
Weighted graphs: Minimum spanning tree.