ALGORITHMS AND DATA STRUCTURES
cod. 14839

Academic year 2014/15
1° year of course - Second semester
Professor
Grazia LOTTI
Academic discipline
Informatica (INF/01)
Field
Discipline informatiche
Type of training activity
Characterising
72 hours
of face-to-face activities
9 credits
hub: PARMA
course unit
in - - -

Learning objectives

The goal of the course is to familiarize students with algorithms, data structures and with the techniques needed for analyzing their efficiency.

Knowledge and understanding:
The main objective of this course is to acquire the tools and techniques needed to analyze and design practical algorithmic solutions to elementary real-world problems. This course gives students an in-depth understanding of a wide range of fundamental algorithms and data structures used in developing structured, efficient, reusable, and practical software.

Applying knowledge and understanding:
Students will be able to compare different algorithms for the same task, and predict or guarantee performance for large problems. Students will be able to study the inherent difficulty of the given problem, to model and implement efficient software solutions using appropriately selected algorithms and data structures.

Prerequisites

- - -

Course unit content

This course presents an introduction to the most important data
structures and to the techniques for designing and analyzing computer algorithms.
General topics include asymptotics, solving recurrence, algorithm design, analysis of algorithms
and data structures.

Full programme

• Undecidability, intractability of computational problems.
• Computational complexity: models of computation, analysis of algorithms.
• Divide and conquer technique, recurrence relations, the main Lemma.
• Basic data structures: linked lists, stacks, queues, trees.
• Comparison-based sorting algorithms: Insertionsort, Mergesort, Quick-
sort, Heapsort.
• Lower bounds for sorting and searching.
• Sorting in linear time.
• Median and order statistics.
• Introduction to dynamic programming and Greedy technique.
• Binary trees, binary search trees, AVL trees, B-trees.
• Hash tables.
• Graphs, BFS,DFS, DAG, topological sort, strong components.
• Union-find, MST, Kruskal’s algorithm, Prim’s algorithm.
• Dijkstra’s algorithm, Bellman-Ford algorithm.

Bibliography

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to algorithms, MIT Press, third edition, 2011.
• C. Demestrescu, I. Finocchi, G. F. Italiano, Algoritmi e strutture dati, McGraw Hill, seconda edizione, 2008.
• P. Crescenzi, G. Gambosi, R. Grossi. Strutture di Dati e Algoritmi, Pearson, prima edizione, 2006

Teaching methods

Class, exercises. Meanwhile (Lab of “Fondamenti di Programmazione B”) some of the most significant data structure are implemented in C++.

Assessment methods and criteria

Written and oral examination. Written examination includes a number of exercises some of which are simple variants of exercises given in class, others are totally new, but can be solved by using the techniques discussed in class.
Students can get the minimum grade by solving the exercises of the first kind.

Other information

- - -

2030 agenda goals for sustainable development

- - -

Contacts

Toll-free number

800 904 084

Student registry office

E. segreteria.scienze@unipr.it
T. 0521 90 5116

Quality assurance office

Education manager
dr. Claudia Buga
T. 0521 90 2842
Office e-mail: smfi.didattica@unipr.it
Manager e-mail: claudia.buga@unipr.it

President of the degree course

Prof. Alessandro Dal Palù
E. alessandro.dalpalu@unipr.it

Faculty advisor

Prof. Vincenzo Arceri
E. vincenzo.arceri@unipr.it

Career guidance delegate

Prof. Roberto Alfieri
E. roberto.alfieri@unipr.it

Tutor Proffesors

Prof. Enea Zaffanella
E. enea.zaffanella@unipr.it

Erasmus Delegates

Prof. Roberto Bagnara
E. roberto.bagnara@unipr.it
Student tutor dr. Anna Macaluso
E. anna.macaluso@studenti.unipr.it

Quality assurance manager

Prof. Roberto Alfieri
E. roberto.alfieri@unipr.it

Internships

Prof. Roberto Alfieri
E. roberto.alfieri@unipr.it

Tutor students

Tutor a.a. 2021-2022 dr. Francesco Manfredi
E. francescosaverio.manfredi@studenti.unipr.it

Student representatives: 
Greta Dolcetti 
Massimo Frati
Davide Tarpini