Corso di Progettazione di Algoritmi

Docente: Annalisa De Bonis

matricole congrue ad uno

a.a. 2022-23

Orario delle lezioni

• Lunedì: 11-13, F1
• Mercoledì: 14-16, S6
• Venerdì: 9-11, F1

Orario di ricevimento

• L'orario di ricevimento aggiornato è pubblicato qui

Libri di testo

• KLEINBERG, TARDOS. ALGORITHM DESIGN. PEARSON ADDISON WESLEY.
• S. DASGUPTA, C. H. PAPADIMITRIOU, AND U. V. VAZIRANI. ALGORITHMS. MCGRAW-HILL

Altri testi utili

• CORMEN, LEISERSON, RIVEST, STEIN. INTRODUCTION TO ALGORITHMS. THE MIT PRESS, MCGRAW-HILL BOOK COMPANY.

Prove in itinere

• NUOVO: Risultati delle prove in itinere

Slide delle lezioni

• Introduzione al corso
• Efficienza degli algoritmi e analisi asintotica degli algoritmi (I parte)
• Efficienza degli algoritmi e analisi asintotica degli algoritmi (II parte)
• Efficienza degli algoritmi e analisi asintotica degli algoritmi (III parte)
• Grafi (I parte: definizioni e proprieta`)
• Grafi (II parte: visita BFS.)
• Grafi (III parte: visita DFS e componenti connesse.)
• Grafi (IV parte: Grafi bipartiti e Ordine topologico di un DAG)i Aggiornata il 17 marzo.
• Algoritmi greedy (I parte: Interval Scheduling, Partizionamento di intervalli)
• Algoritmi greedy (II parte: Minimizzazione dei Ritardi, Problema del taglio del tubo)
• Algoritmi greedy (III parte: Algoritmo di Dijkstra)
• Algoritmi greedy (IV parte: MST ed algoritmo di Prim) AGGIORNATO AL 30 MARZO
• Algoritmi greedy (V parte: Algoritmo di Kruskal)
• Nota su notazioni asintotiche
• Esercitazione
• Algoritmi greedy (VI parte: Algoritmo Inverti-Cancella, k-clustering,caching offline)
• Divide et impera (I parte)
• Divide et impera (II parte)
• Divide et impera (III parte)
• Divide et impera (IV parte)
• Programmazione dinamica (I parte: Interval Scheduling Pesato)
• Programmazione dinamica (II parte: Subset Sums, Problema dello zaino)
• Programmazione dinamica (III parte: Minimum Coin Change Problem, Coin Change Problem, Sottosequenza Comune Più Lunga)
• Programmazione dinamica (IV parte: Algoritmo di Bellman-Ford per i cammini minimi)
• Programmazione dinamica (V parte: Segmented Least Squares, Sottosequenza crescente più lunga)
• Programmazione dinamica (VI parte: Sottosequenza crescente più lunga (continuazione), Allineamento di sequenze)
• Programmazione dinamica (VII parte: Moltiplicazione di matrici e 3 altri esempi)
• Problemi difficili e ricerca esaustiva intelligente.

Appelli

Avvisi:

• 7 giugno 2023. Gli studenti che hanno sostenuto le due prove in itinere NON devono partecipare alla prova dell'8/6. Le persone che hanno superato le prove saranno convocate per la discussione con un avviso all'interno del file contenente la lista degli ammessi. Controllate questo sito tra domani e dopodomani.


• 15 maggio 2023. Tutti gli studenti che hanno sostenuto la prima prova in itinere (compresi quelli degli anni diversi dal II) e sono intenzionati a sostenere la seconda prova devono inviare un'UNICA email ad algoritmi2023@gmail.com entro il 20 maggio 2023 con il testo VUOTO e con in oggetto cognome, nome, numero di matricola (in questo ordine e separati da virgola). Cognome e nome devono essere scritti in maiuscolo e senza spazi nei nomi e cognomi composti La matricola deve essere riportata per intero senza trattini, spazi o altri caratteri tra le cifre. Ad esempio, lo studente De Rossi Marco Antonio 0512108593 inviera` la mail con oggetto "DEROSSI, MARCOANTONIO, 0512108593"
  Le mail che non rispetteranno questo formato saranno ignorate cosi` come pure mail multiple inviate dalla stessa persona.
• 2 maggio 2023 aggiornato al 3 maggio. È stato creato il team del tutorato a cui si può aderire attraverso il seguente token: vn94g4x .
  Gli studenti interessati a seguire il tutorato sono pregati di aderire al team quanto prima (entro il 4 maggio) per decidere insieme al tutor l'orario delle lezioni attraverso la form che il tutor renderà disponibile.
• 14 marzo 2023. Mercoledì 15 marzo non ci sarà lezione per le celebrazioni del cinquantenario.