CODE 80306 2023/2024 6 cfu anno 2 INFORMATICA 8759 (L-31) - GENOVA INF/01 Italian GENOVA 2° Semester Per sostenere l'esame di questo insegnamento è necessario aver sostenuto i seguenti esami: Computer Science 8759 (coorte 2022/2023) ALGORITHMS AND DATA STRUCTURES 80298 2022 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.

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.

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

Lecture notes.

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

TEACHERS AND EXAM BOARD

Exam Board

ELENA ZUCCA SCHILLANI (President)

PAOLA MAGILLO

ALESSANDRO VERRI (President Substitute)

LESSONS

Class schedule

ALGORITHM ANALYSIS AND DESIGN

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.

Exam schedule

Data appello Orario Luogo Degree type Note
18/01/2024 09:00 GENOVA Scritto
01/02/2024 09:00 GENOVA Scritto
17/06/2024 09:00 GENOVA Scritto
04/07/2024 09:00 GENOVA Scritto
04/09/2024 09:00 GENOVA Scritto
16/01/2025 09:00 GENOVA Scritto
30/01/2025 09:00 GENOVA Scritto