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.
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.
At the end of the course the student will be able to:
Basic knowledge of algorithms and data structures.
Traditional.
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
Lecture notes.
Introduction to algorithms and data structures. Cormen, Leiserson, Rivest, Stein. McGraw Hill.
Ricevimento: Appointment by email
Ricevimento: Appointment by email: enrico.puppo@unige.it During class period appointments for groups can be set by posting on the course forum on AulaWeb.
ENRICO PUPPO (President)
ALESSANDRO VERRI (President)
According to the calendar approved by the Degree Program Board: https://corsi.unige.it/en/corsi/8759/studenti-orario
ALGORITHM ANALYSIS AND DESIGN
Written and oral exam.
Guidelines for students with certified Specific Learning Disorders, disabilities, or other special educational needs are available at https://corsi.unige.it/en/corsi/8759/studenti-disabilita-dsa
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.
For further information, please refer to the course’s AulaWeb module or contact the instructor.
