Corso Algoritmi e Strutture Dati Python

Lezione 1 • Funzioni e ambito di visibilità

Definisce funzioni riutilizzabili, argomenti predefiniti e regole di ambito delle variabili. Le funzioni sono l'unità primaria di implementazione degli algoritmi in questo corso.

Lezione 2 • Panoramica sulle collezioni incorporate

Esamina liste, tuple, dizionari e insiemi con le loro complessità temporali. Fornisce la conoscenza pratica sui container necessaria prima di costruire strutture personalizzate.

Lezione 3 • Moduli, librerie e I/O

Introduce l'importazione di moduli, l'uso della libreria standard e la lettura dell'input per problemi in stile competitivo. Prepara gli studenti a flussi di lavoro strutturati di problem-solving.

Lezione 1 • O-grande, Theta-grande e Omega-grande

Definisce le tre notazioni asintotiche e il loro significato matematico. Lo studente applica ciascuna notazione per classificare con precisione il comportamento degli algoritmi.

Lezione 2 • Misurazione delle prestazioni degli algoritmi

Introduce i concetti di misurazione del runtime e spiega perché l'analisi teorica supera il solo benchmarking. Stabilisce la mentalità analitica per ogni capitolo successivo.

Lezione 3 • Analisi di cicli e ricorsione

Insegna l'analisi sistematica di cicli annidati e chiamate ricorsive. Direttamente applicabile a ogni algoritmo di ordinamento e ricerca nei capitoli successivi.

Lezione 1 • Two-pointer e sliding window

Introduce i pattern two-pointer e sliding window per soluzioni O(n) su dati ordinati o sequenziali. Riduce significativamente gli approcci a forza bruta O(n²).

Lezione 2 • Tabelle hash e gestione delle collisioni

Spiega la progettazione della funzione hash, la risoluzione delle collisioni e il funzionamento interno dei dict di Python. Lo studente implementa mappe hash personalizzate e risolve problemi di ricerca in O(1).

Lezione 3 • Tecniche di manipolazione degli array

Tratta operazioni in-place, somme prefisse e array differenza per query su intervalli. Questi pattern compaiono nella maggior parte dei problemi in stile colloquio.

Lezione 1 • Coda, deque e coda con priorità

Implementa code FIFO, code a doppia estremità (deque) e code con priorità basate su heap. Prepara lo studente a problemi di BFS e algoritmi di scheduling.

Lezione 2 • Liste concatenate semplici e doppie

Costruisce classi per liste concatenate basate su nodi con inserimento, eliminazione e attraversamento. Stabilisce le competenze di manipolazione dei puntatori utilizzate successivamente in alberi e grafi.

Lezione 3 • Implementazione di stack e applicazioni

Implementa stack utilizzando liste e liste concatenate, applicandoli poi a problemi di parsing e valutazione. Gli stack sono alla base della simulazione della ricorsione e del backtracking.

Lezione 1 • Fondamenti della ricorsione

Definisce i casi base, le chiamate ricorsive e il comportamento dello stack di chiamate con tracciamento visivo. Una progettazione corretta della ricorsione è un prerequisito per divide-and-conquer e backtracking.

Lezione 2 • Ordinamento divide and conquer

Implementa merge sort e quicksort con analisi completa della ricorrenza. Lo studente comprende le strategie di partizionamento e i trade-off di stabilità.

Lezione 3 • Algoritmi di ricerca

Implementa la ricerca binaria e le sue varianti su array ordinati e spazi di risposta. La ricerca binaria sulla risposta è un pattern chiave per problemi di ottimizzazione.

Lezione 1 • Pattern per problemi su alberi

Tratta problemi di somma di percorso, antenato comune più basso e diametro utilizzando la ricorsione. Questi pattern compaiono frequentemente nei colloqui tecnici e nella progettazione di sistema.

Lezione 2 • Trie e alberi segmento

Costruisce trie di prefissi per la ricerca su stringhe e alberi segmento per query su intervalli. Questi alberi specializzati risolvono problemi che BST e heap non possono gestire in modo efficiente.

Lezione 3 • Alberi bilanciati e heap

Introduce i concetti di bilanciamento degli alberi AVL e rosso-nero e la struttura heap. Lo studente capisce quando gli alberi auto-bilancianti sono necessari per garantire le prestazioni.

Lezione 4 • Fondamenti degli alberi binari

Definisce la terminologia degli alberi, la struttura dei nodi e gli ordini di attraversamento ricorsivo. I pattern di attraversamento sono il fondamento di tutti gli algoritmi basati su alberi.

Lezione 1 • Ordinamento topologico e rilevamento di cicli

Applica l'algoritmo di Kahn e l'ordinamento topologico basato su DFS ai DAG. Il rilevamento dei cicli e l'ordinamento sono essenziali per i problemi di risoluzione delle dipendenze.

Lezione 2 • Alberi di copertura minimi e Union-Find

Implementa gli algoritmi di Kruskal e Prim insieme alla struttura Union-Find. Questi strumenti risolvono in modo efficiente problemi di connettività di rete e clustering.

Lezione 3 • Algoritmi di cammini minimi

Implementa Dijkstra, Bellman-Ford e Floyd-Warshall per grafi pesati. Lo studente seleziona l'algoritmo corretto in base alle proprietà e ai vincoli del grafo.

Lezione 4 • Attraversamenti BFS e DFS

Implementa BFS iterativa e DFS ricorsiva con tracciamento dei nodi visitati. Questi due attraversamenti sono alla base di quasi ogni algoritmo sui grafi in questo capitolo.

Lezione 1 • Pattern classici di problemi DP

Risolve i problemi dello zaino, della sottosequenza più lunga e del cambio di monete come modelli DP canonici. Padroneggiare questi modelli accelera la risoluzione di nuovi problemi DP.

Lezione 2 • Fondamenti di DP e memoization

Definisce i sottoproblemi sovrapposti e la sottostruttura ottima come prerequisiti per la DP. La memoization top-down converte soluzioni ricorsive in soluzioni DP efficienti.

Lezione 3 • Tabulazione e ottimizzazione dello spazio

Costruisce tabelle DP bottom-up e riduce lo spazio utilizzando array a scorrimento. La DP con spazio ottimizzato è fondamentale per vincoli di input grandi nei problemi competitivi.

Lezione 4 • DP su intervalli e griglie

Applica la DP a problemi di unione di intervalli e percorsi su griglia con spazi di stato 2D. Questi pattern estendono le competenze DP a tipi di problemi basati su matrici e intervalli.