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. 2020-2021
  6. 3rd year
  1. Design and Analysis of Algorithms
  2. Summary
Insegnamento Course full name
Design and Analysis of Algorithms
Course ID number
2021-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.

Accenni ai problemi Np-Completi e complessità di approssimazione.  

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 la ricerca su grafi, la ricerca di cammini minimi, la costruzione di alberi di copertura minimi.

Programma esteso

1.  Strumenti matematici

Crescita delle funzioni, notazioni asintotiche
Calcolo del tempo di esecuzione per algoritmi iterativi
Richiami sulla ricorsione: calcolo del fattoriale
Ricorrenze e tempi di calcolo di algoritmi ricorsivi
Ricerca dicotomica, calcolo altezza di un albero binario

2.  Tecniche algoritmiche: Programmazione Dinamica (DP)

 Esempi introduttivi
 Caratteristiche principali - Ricorsione
 Implementazione con matrici

3.  Tecniche algoritmiche: il metodo Greedy (goloso)

Esempi introduttivi
I codici di Huffman
Matroidi
Teorema di Rado

4. Algoritmi su grafi

Rappresentazione dei grafi.
Visita in ampiezza dei grafi
Visita in profondità dei grafi

5. Alberi di copertura minimi

Algoritmo di Kruskal
Algoritmo di Prim

5. Problemi di cammino minimo
Algoritmo di Dijkstra
Algoritmo di Bellman-Ford
Algoritmo di Floyd-Warshall

6.  Problemi di flusso massimo

Algoritmo di Ford-Fulkerson

7.  NP completezza e riducibilità. Approssimazione.

Il problema Vertex-cover.

Prerequisiti

Nozioni  base di programmazione, algoritmi e strutture dati

Modalità didattica

Nel periodo di emergenza Covid-19 le lezioni ed esercitazioni saranno videoregistrate (alcune di esse potranno essere trasmesse in modalità sincrona); ci saranno inoltre dei momenti sincroni (in streaming, non registrati) di discussione e risposta alle domande degli studenti.

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:  la valutazione massima della prova scritta è 30/30. Tale prova consiste in due parti ciascuna sulla prima e seconda parte del corso e consistono in:

-  esercizi relativi ai contenuti del corso

- domande aperte relative alle nozioni teoriche presentate a lezione

Possono essere assegnati fino a 2 punti aggiuntivi in caso di esercizi svolti particolarmente bene.

Prove parziali:

La prova scritta puo' essere sostituita da due prove parziali, che si tengono a meta' corso.   

Ogni prova parziale ha valutazione massima 15/15: il voto finale si ottiene sommando i voti delle due prove parziali. 

Possono essere assegnati fino a 2 punti aggiuntivi (totali per le due prove) in caso di esercizi svolti particolarmente bene.


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.

We introduce the NP-complexity and approximation algorithms.

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 graph search, minimum spanning trees construction, Shortest path problems will be presented.

Detailed program

1.  Mathematical tools

  • Growth of functions, asymptotic notations
  • Execution time of iterative algorithms
  • Recurrence equations and Execution times of recursive algorithms
  • Dichotomic Search, height of a binary tree


2.  Algorithmic Techniques: Dynamic Programming (DP)

  •  Introductory examples
  •  Main features - Recursion
  •  Implementation with matrices


3.  Algorithmic Techniques: Greedy method

  • Introductory examples
  • Huffman Codes
  • Matroids
  • Rado Theorem


4. Graph Algorithms

  • Representations of graphs.
  • Breadth first visit of graphs
  • Depth first visit of graphs


5. Minimum spanning trees

  • Kruskal algorithm
  • Prim algorithm


5. Shortest path problems

  • Dijkstra Algorithm
  • Bellman-Ford Algorithm
  • Floyd-Warshall Algorithm


6.  Maximum flow problems

  • Ford-Fulkerson Algorithm


7.  NP completeness and reducibility. Approximation.

Approximation of Vertex-cover. 


Prerequisites

Basic notions of programming, algorithms and data structures

Teaching form

During the Covid-19 emergency, lectures and practice exercices will be recorded (some of them could be online). There will be some discussions and answers to questions in streaming and not recorded

The course is in Italian.

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 slides and exercises are available through the e-learning website.


Semester

First semester

Assessment method

Written examination:  the total score is 30/30. The exam consists of two parts, relative to two parts of the course and consisting in:

-  exercises related to the main arguments

- open questions on the theoretical aspects of the arguments discussed in the course

 2 additional points may be assigned if the exercises are  perfectly solved 

Partial written examinations:

The written exam can be substituted by two partial written examinations during the course

Each partial written examination has a maximum score of  15/15:  the final score of the exam is the sum of the two partial scores.

 2 additional points may be assigned if the exercises are  perfectly solved 



Office hours

By appointment

Enter

Key information

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

Staff

    Teacher

  • PB
    Paola Bonizzoni
  • RR
    Raffaella Rizzi
  • Assistant

  • AD
    Alberto Dennunzio
  • CZ
    Claudio Zandron

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