Se non diversamente specificato, le mattine (AM) sono in orario 09:00 - 13:00 e i pomeriggi (PM) sono in orario 15:00 - 19:00.
¶ Lezione ed esercitazione: square root decomposition (Alessandro Bortolin & Davide Bartoli)
Materiale:
Problemi:
¶ Lezione ed esercitazione: geometria computazionale (Alessandro Bortolin & Davide Bartoli)
Materiale:
Problemi:
Assistenza: Giorgio Audrito & Carlo Collodel
-
Bound classici (numero di fattori primi, numero di divisori, valori distinti di ⌊n/i⌋)
-
Stars and Bars
-
Principio di Inclusione-Esclusione
-
Numeri di Catalan e generalizzazioni
-
Funzione di Mobius
Materiale:
Problemi:
Problemi avanzati (circa in ordine di difficoltà):
- MinQueue
- Binary Heap
- Balanced Search Trees
- Policy-based data structures nelle STL
Materiale:
Problemi:
Problemi avanzati:
- Concetti base stringhe (alfabeto, suffisso, prefisso, ecc.)
- Problema del matching
- Z-array e algoritmo Z
- Algoritmo di hashing di Rabin-Karp
- Suffix array
- Dictionary of Basic Factors
Materiale:
Problemi:
Problemi avanzati (circa in ordine di difficoltà):
- Small to Large
- Heavy-Light Decomposition
- Centroid Decomposition
Materiale:
Problemi:
Problemi avanzati:
- Various tricks with segment trees
- Algoritmo per componenti fortemente connesse
- How many (non-simple) paths from A to B?
Materiale:
Problemi:
- Sum over Subsets (SOS) DP
- Connected Components DP
- Slope Trick
- Square Tree DP
- Divide and Conquer DP
Materiale:
Problemi:
Problemi avanzati (circa in ordine di difficoltà):
- Risolto (o tentato di risolvere) i tre problemi che si trovano nel google doc.
- È stata presentata velocemente la teoria delle ricorsioni lineari (esponenziazione di matrici, polinomio caratteristico, accenno a Berlekamp-Massey).
Materiale:
Assistenza: Luca Versari & Filippo Casarin
- Strutture persistenti: stack, segment tree, bbst/array, DSU
- Numero di punti in un rettangolo
- Queue persistente: perchè non funziona nel modo banale
Materiale:
Problemi:
Problemi:
- Problema del flusso massimo
- Algoritmo di Ford-Fulkerson
- Algoritmo di Edmonds-Karp
- Dualità flusso massimo e taglio minimo
- Problema del flusso massimo a costo minimo
- Algoritmo per il flusso massimo a costo minimo con costi positivi
- Problema del massimo matching bipartito
- Problema della minima vertex cover bipartita
Materiale:
Problemi:
Assistenza: Tommaso Dossi & Davide Bartoli
Materiale:
Problemi: