Skip to main content
If you continue browsing this website, you agree to our policies:
  • Condizioni di utilizzo e trattamento dei dati
Continue
x
If you continue browsing this website, you agree to our policies:
  • Condizioni di utilizzo e trattamento dei dati
Continue
x
e-Learning - UNIMIB
  • Home
  • More
Listen to this page using ReadSpeaker
English ‎(en)‎
English ‎(en)‎ Italiano ‎(it)‎
 Log in
e-Learning - UNIMIB
Home
Percorso della pagina
  1. Science
  2. Bachelor Degree
  3. Informatica [E3102Q - E3101Q]
  4. Courses
  5. A.A. 2024-2025
  6. 3rd year
  1. Design and Analysis of Algorithms
  2. Summary
Insegnamento Course full name
Design and Analysis of Algorithms
Course ID number
2425-3-E3101Q113
Course summary SYLLABUS

Course Syllabus

  • Italiano ‎(it)‎
  • English ‎(en)‎
Export

Obiettivi

Gli studenti acquisiranno la conoscenza delle principali tecniche di progetto e analisi degli algoritmi e la capacità di individuare le più idonee tecniche algoritmiche per la soluzione efficiente di specifici problemi computazionali.

Contenuti sintetici

L'insegnamento intende introdurre le principali tecniche algoritmiche (programmazione dinamica, greedy), con particolare attenzione agli aspetti di efficienza degli algoritmi, con i relativi strumenti di analisi. Verranno illustrati i principali algoritmi per risolvere vari problemi di ottimizzazione combinatoria specialmente su insiemi, sequenze e grafi, tra cui la ricerca di cammini minimi in un grafo pesato e la costruzione di alberi di copertura minimi.

Programma esteso

1. Strumenti matematici (ripasso)

  • Crescita delle funzioni, notazioni asintotiche
  • Calcolo del tempo di esecuzione per algoritmi iterativi
  • Ricorsione e algoritmi ricorsivi
  • Ricorrenze e tempi di calcolo di algoritmi ricorsivi

2. Tecniche algoritmiche: Programmazione Dinamica (DP)

  • Esempi introduttivi
  • Caratteristiche principali - Ricorsione
  • Implementazione con matrici
  • Problemi di ottimizzazione combinatoria su sequenze e insiemi

3. Tecniche algoritmiche: il metodo Greedy (goloso)

  • Esempi introduttivi
  • Matroidi
  • Teorema di Rado

4\ Strutture dati per insiemi digiunti

  • Definizioni e operazioni
  • Rappresentazione mediante liste concatenate e mediante foreste

5. Alberi di copertura minimi

  • Algoritmo di Kruskal
  • Algoritmo di Prim

5. Problemi di cammino minimo

  • Algoritmo di Dijkstra
  • Algoritmo di Floyd-Warshall

6. Tabelle Hash

  • Tabelle ad indirizzamento diretto
  • Tabelle Hash

7. Introduzione a NP completezza e riduzioni

  • problemi NP completi
  • riduzione tra problemi

Prerequisiti

Nozioni base di programmazione, algoritmi e strutture dati

Modalità didattica

Lezioni, esercitazioni e esercitazioni laboratoriali in aula.
Le Lezioni prevedono una modalità didattica erogativa.
Le ore di esercitazioni ed esercitazioni laboratoriali prevedono una modalità didattica erogativa ed interattiva.

La lingua del corso è l'italiano.

Materiale didattico

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, Ed. Mc. Graw Hill

Materiale integrativo (lucidi ed esercizi) disponibili sul sito e-learning.

Periodo di erogazione dell'insegnamento

Primo semestre

Modalità di verifica del profitto e valutazione

Prova scritta: Essa consiste di:

- esercizi relativi ai contenuti del corso

- domande aperte relative alle nozioni teoriche presentate a lezione

La valutazione totale massima derivante da esercizi e domande aperte è di 31 punti.
L'esame è considerato superato se la valutazione finale è di almeno 18.
Possono essere assegnati ulteriori 3 punti aggiuntivi (relativi ad una domanda/esercizio facoltativo).
Il punteggio finale dà automaticamente origine al voto in trentesimi (30 e lode per punteggi superiori a 30).

Prove parziali:
La prova scritta puo' essere sostituita da due prove parziali, che si tengono a meta' e fine corso.
Ogni prova parziale verte sugli argomenti trattati nella corrispondente parte del corso. Consiste di esercizi e domande aperte relative alle nozioni teoriche presentate a lezione.

Ogni prova parziale ha valutazione massima di 31 punti: la valutazione finale si ottiene dalla media dei voti delle due prove parziali. L'esame è considerato superato se la valutazione di ogni prova parziale è maggiore di 14 e la valutazione finale è di almeno 18.
Possono essere assegnati ulteriori 3 punti aggiuntivi (relativi ad una domanda/esercizio facoltativo).

Il punteggio finale corrisponderà esattamente al voto in trentesimi (30 e lode per punteggi superiori a 30).

Orario di ricevimento

su appuntamento

Export

Aims

Students will acquire knowledge of the main techniques for the design and analysis of algorithms and the ability to identify the most appropriate algorithmic techniques to efficiently solve specific computational problems.

Contents

The course will introduce the main algorithmic techniques (dynamic programming, greedy), with particular attention to the efficiency of the algorithms, with the main analysis methods. The main algorithms for several combinatorial optimization problems, especially over sets, sequences, and graphs will be presented, including minimum spanning trees construction and shortest path problems.

Detailed program

1. Mathematical tools (review)

  • Growth of functions, asymptotic notations
  • Execution time of iterative algorithms
  • Recursion and recursive algorithms
  • Recurrence equations and Execution times of recursive algorithms

2. Algorithmic Techniques: Dynamic Programming (DP)

  • Introductory examples
  • Main features - Recursion
  • Implementation with matrices
  • Combinatorial optimization problems over sequences and sets

3. Algorithmic Techniques: Greedy method

  • Introductory examples
  • Matroids
  • Rado Theorem

4. Disjoint-set data structure

  • Definitions and operations
  • Linked list representation and forest representation

5. Minimum spanning trees

  • Kruskal algorithm
  • Prim algorithm

5. Shortest path problems

  • Dijkstra Algorithm
  • Floyd-Warshall Algorithm

6. Hash Tables

  • Direct-address tables
  • Hash tables

7. Introduction to NP-completeness and reducibility

  • NP-complet problems
  • Reducibility

Prerequisites

Basic notions of programming, algorithms and data structures

Teaching form

Lectures, practice exercises, and classroom laboratory exercises in presence. The course is in Italian.
Lectures will be carried out in a traditional lecture mode while practice exercises and classroom laboratory exercises in both traditional and interactive mode.

Textbook and teaching resource

T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, Ed. Mc. Graw Hill

Further material and exercises are available through the e-learning website.

Semester

First semester

Assessment method

Written examination: It consitsts of

- exercises related to the main topics

- open questions on the theoretical aspects of the topics explained in the course

The maximum total score deriving from exercises and open questions is 31 points.
The exam is passed only if the final score is at least equal to 18.
3 additional points may be assigned (related to an optional exercise/open question).
The final score will just correspond to the usual score expressed in thirtieths (30 e lode if the final score is greater than 30).

Partial written examinations:
The written exam can be substituted by two partial written examinations in the middle and at the end of the course.

Each partial written examination is about the topics of the corresponding part of the course and it consists of exercises to the main topics and open questions on the related theoretical aspects.

Each partial written examination has a maximum score of 31/31: the final score of the exam is the average of the two partial scores. The exam is passed only if the score of each partial examination is greater than 14 and the final score is at least equal to 18.
3 additional points may be assigned (related to an optional exercise/open question).

The final score will just correspond to the usual score expressed in thirtieths (30 e lode if the final score is greater than 30).

Office hours

By appointment

Enter

Key information

Field of research
INF/01
ECTS
8
Term
First semester
Activity type
Mandatory
Course Length (Hours)
0
Degree Course Type
Degree Course
Language
Italian

Staff

    Teacher

  • PB
    Paola Bonizzoni
  • AD
    Alberto Dennunzio
  • RR
    Raffaella Rizzi
  • Tutor

  • TT
    Telemaco Terzi
  • AV
    Alberto Varisco

Students' opinion

View previous A.Y. opinion

Bibliography

Find the books for this course in the Library

Enrolment methods

Manual enrolments
Self enrolment (Student)

You are not logged in. (Log in)
Policies
Get the mobile app
Powered by Moodle
© 2025 Università degli Studi di Milano-Bicocca
  • Privacy policy
  • Accessibility
  • Statistics