Vai al contenuto principale Vai al footer
Università degli Studi di Parma Università degli Studi di Parma
Degree course in
Mathematics
Università degli Studi di Parma
Department of Mathematical, Physical and Computer Sciences

ALGORITHMS AND DATA STRUCTURES
cod. 14839

borrowed from Corso di Laurea in INFORMATICA - ALGORITMI E STRUTTURE DATI I - cod. 14839
Academic year 2012/13
2° year of course - Second semester
Professor
Grazia LOTTI
Academic discipline
Informatica (INF/01)
Field
Attività formative affini o integrative
Type of training activity
Related/supplementary
63 hours
of face-to-face activities
9 credits
hub: PARMA
course unit
in - - -
lectures timetable unavailable
exam calls
Print

Learning objectives

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

Prerequisites

- - -

Course unit content

This course presents an introduction to the most important data structures and
to the techniques for designing efficient 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. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms,
McGraw-Hill;
• C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e strutture dati,
McGraw-Hill;
• R. Sedgwick, Algorithms in C++, Princeton University.

Teaching methods

Lessons, exercises and Lab.

Assessment methods and criteria

Written and oral exam.

Other information

- - -

2030 agenda goals for sustainable development

- - -

Contacts

Toll-free number

800 904 084

Student registry office

E. segreteria.scienze@unipr.it
T. +39 0521 905116

Quality assurance office

Education manager
dott.ssa Giulia Bonamartini
T. +39 0521 906968
E. servizio smfi.didattica@unipr.it
E. del manager giulia.bonamartini@unipr.it

President of the degree course

Prof. Luca Lorenzi
E. luca.lorenzi@unipr.it

Faculty advisor

Prof. Luca Lorenzi
E. luca.lorenzi@unipr.it

Career guidance delegate

Prof. Francesco Morandin
E. francesco.morandin@unipr.it

Tutor Professors

Prof. Emilio Acerbi
E. emilio.acerbi@unipr.it

Prof. Marino Belloni
E. marino.belloni@unipr.it

Prof.ssa Maria Groppi
E. maria.groppi@unipr.it

Prof.ssa Chiara Guardasoni
E. chiara.guardasoni@unipr.it

Prof. Luca Lorenzi
E. luca.lorenzi@unipr.it

Prof. Costantino Medori
E. costantino.medori@unipr.it

Prof. Adriano Tomassini
E. adriano.tomassini@unipr.it

Erasmus delegates

Prof.ssa Fiorenza Morini
E. fiorenza.morini@unipr.it

Quality assurance manager

Prof.ssa Maria Groppi
E. maria.groppi@unipr.it

Tutor students

Dott. Matteo Mezzadri
E. matteo.mezzadri@studenti.unipr.it