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.
Materiale:
Problemi:
Risorse extra:
¶ Lezione / esercitazione gruppo avanzato: Divide and Conquer (Valerio Stancanelli)
Materiale:
Problemi (circa in ordine di difficoltà):
- Bug concettuali
- Utilizzo di
cout e macro #ifdef per il debugging
- Uso di
-fsanitize per trovare letture/scritture fuori memoria e undefined behaviours
- Funzionamento del comando
perf e di valgrind
- Bug di conversione implicita
- Esempi di bug specifici:
- Accedere a
next(it) senza controllare next(it) != vec.end()
- Problemi derivanti dall'includere/escludere estremi
- Relazione d'ordine non antiriflessiva in una comparison lambda per
std::sort
- Valore troppo basso della variabile
INF
- Passaggio per copia anziché per reference
Materiale:
- Cos'è un grafo, definizione formale
- Rappresentazioni di grafi in un programma: elenco di archi, matrice di adiacenza, liste di adiacenza
- Visite:
- Alberi: definizioni, alberi radicati, aggiunta di un arco a un albero
- Grafi funzionali: proprietà delle componenti connesse, relazione con albero + arco
- Grafi pesati e cammini minimi:
- Bellman-Ford
- Floyd-Warshall
- Dijkstra
- DAG e ordinamento topologico:
- Algoritmo e dimostrazione intuitiva di correttezza
- Non unicità
- Articulation points
- Bridges
Materiale:
Esercizi:
Problemi (circa in ordine di difficoltà):
Problemi:
Materiale:
Materiale:
Problema di esempio:
Problemi (circa in ordine di difficoltà):
- breve introduzione alla Standard Library (e come usarla al meglio)
- Disjoint-Set Union
- somme su un range: Segment Tree (e generalizzazione)
- range-query/range-update: lazy propagation
- array *tanto* grandi:
- compressione degli indici
- segment sparsi
Materiale:
Problemi:
- Range query meno classiche:
- Altre strutture dati:
- Bonus (?):
- IOI13_GAME se vi piacciono le range query 2D in meno di Θ(Nlog2N) memoria (non giudico).
Problemi (circa in ordine di difficoltà):
Problemi:
Materiale:
Problemi:
Codice scritto:
Problemi (circa in ordine di difficoltà):
Materiale:
Problemi (circa in ordine di difficoltà):