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 exam with interrogation on the whole program and the discussion of a project to be developed in small groups (2-3 people).
The project must be carried out in Java and the topic will be assigned after 70% of the laboratory exercises have been carried out.
To access the oral exam it is necessary to pass the written test.
In February, an intermediate evaluation test is carried out on the half of the program carried out: this test consists of a written exam with theoretical questions and exercises. Passing this test allows the student to take the final written and oral exam only on the second half of the program.
On the course website are proposed activities (tests and tasks): their development during the course will increase by one point 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.