Schema della sezione

  • Lezione 19: 12/11/25

    • Definizione di Mappa; applicazioni; interfaccia Map.
    • Implementazione di una Mappa tramite lista position-based o array di taglia |U|, con la complessità dei metodi get, put e remove.
    • Tabelle Hash: ingredienti principali; nozione di uniform hashing; scelta dell'hash code; scelta della compression function; risoluzione collisioni tramite separate chaining; cenni su open addressing.
     
    Lezione 20:  13/11/25
     
    • Tabelle Hash: implementazione dei metodi get(k), put(k,x) e remove(k); definizione di load factor; complessità dei metodi get(k), put(k,x) e remove(k) al caso pessimo e a caso medio in funzione del load factor; analisi del costo medio di ricerca di una chiave non presente in una tabella hash; rehashing con analisi ammortizzata.
    • Alberi Binari di Ricerca (ABR): definizione; proprietà della vista in-order; metodo TreeSearch(k,v) e sua complessità; implementazione del metodo get(k) e sua analisi. 
     
    Lezione 21:  18/11/25
     
    • Alberi Binari di Ricerca (ABR): implementazione dei metodi della mappa put(k,x) e remove(k), e loro analisi.
    • Esercizi: versione iterativa di TreeSearch.
    • Multi-Way Search Tree: definizione ed esempi; Proposizione 11.2 (ed esercizio C-11.46) del testo; metodo MWTreeSearch(k,v).

     

    Lezione 22:  19/11/25

     

    • Multi-Way Search Tree: metodo get(k); analisi di MWTreeSearch(k,v) e get(k) in funzione dell'altezza h e del massimo numero di figli di un nodo dmax.
    • (2,4)-Tree: definzione, altezza (Proposizione 11.3 del testo) e complessità del metodo get(k).
    • Implementazione del metodo put(k,x) (con Split) e sua complessità.
    • Esempi di esecuzione di put(k,x) su un (2,4)-Tree.
    • Metodo remove(k): idea.

    Lezione 23:  20/11/25

    • Metodo remove(k): pseudocodice; descrizione di Delete; esempi; analisi della complessità.
    • Red-Black Tree: definizione; relazione con il (2,4)-Tree; altezza e complessità dei metodi get, put e remove (senza dimostrazione).
    • Multimappa: definizione; motivazione; specifica dei metodi get(k), put(k,v), remove(k,v); implementazione tramite Mappa e Lista position-based.
     
    Lezione 24:  25/11/25

    • Multimappa: esempio di applicazione dei metodi; complessità dei metodi.
    • Esercizi: algoritmo 24Height (Slide 83 - Parte 2); algoritmo CountLE con variabili size (Slide 73 - Parte 1) e con/senza metodo T.size (primi due esercizi di Slide 81 - Parte 1); algoritmo MinPositive (secondo esercizio di Slide 80 - Parte 1). 
     
    Lezione 25:  26/11/25

    • Esercizi: algoritmo MinMatStraniero (Slide 82 - Parte 1); algoritmo MostFrequentWord (Slide 5 - Parte 1, e Slide 87 - Parte 2); algoritmo 24TreeMergeEq (primo esercizio di Slide 88 - Parte 2); cenni sulla generalizzazione di 24TreeMergeEq al caso di alberi con altezze differenti (secondo esercizio di Slide 88 - Parte 2).
     
    Materiale: