Skip to main content
CODE 80306
ACADEMIC YEAR 2025/2026
CREDITS
SCIENTIFIC DISCIPLINARY SECTOR INF/01
LANGUAGE Italian
TEACHING LOCATION
  • GENOVA
SEMESTER 2° Semester
PREREQUISITES
Propedeuticità in ingresso
Per sostenere l'esame di questo insegnamento è necessario aver sostenuto i seguenti esami:
TEACHING MATERIALS AULAWEB

OVERVIEW

The aim of the course is to learn classical data structures and algorithms, and to analyze their correctness and efficiency. Base notions on complexity and elementary data structures are assumed as prerequisites. 

Since the course is given in italian, please have a look at the italian version of this page for further information.

AIMS AND CONTENT

LEARNING OUTCOMES

To learn classical data structures and algorithms, and to be able to analyze their correctness and efficiency. Base notions on complexity and elementary data structures are assumed as prerequisites. Topics include design and analisys techniques, sorting algorithms, advanced data structures, graph algorithms, NP-completeness.

 

AIMS AND LEARNING OUTCOMES

At the end of the course the student will be able to:

  • Know classical algorithms and algorithmic schemes.
  • Analyze correctness and efficiency of an algorithm.
  • Appreciate the potential of randomization in algorithm design through simple examples.

PREREQUISITES

Basic knowledge of algorithms and data structures.

TEACHING METHODS

Traditional.

SYLLABUS/CONTENT

Design and analysis techniques, asymptotic notations, correctness and complexity of recursive and iterative algorithms, divide-et-impera, dynamic programming, greedy algoritms.

Sorting: simple sorts, mergesort, quicksort, heapsort, lower bound for comparison-based sorting algorithms, linear sorts.

Advanced data structures: heaps, union-find structures.

Graphs: definitions, representations, visits, topological sorting, strongly-connected components, single-source shortest paths (Dijkstra algorithm), minimum spanning tree (Prim and Kruskal algorithms). 

Theory of NP-completeness: complexity classes, NP-complete problems, approximation algorithms

 

RECOMMENDED READING/BIBLIOGRAPHY

Lecture notes.

Introduction to algorithms and data structures. Cormen, Leiserson, Rivest, Stein. McGraw Hill. 

TEACHERS AND EXAM BOARD

LESSONS

LESSONS START

According to the calendar approved by the Degree Program Board: https://corsi.unige.it/corsi/8759/studenti-orario

 

EXAMS

EXAM DESCRIPTION

Written and oral exam.

ASSESSMENT METHODS

The written exam checks the ability of the student to apply in practice learned notions.

The oral exam checks the understanding of concepts and the ability to appropriately illustrate learned notions.

 

FURTHER INFORMATION

Contact the instructor for any additional information not included in the course description.