Weekly outline

  • SCP4065531 - ALGORITMI E STRUTTURE DATI 2022-2023 - PROF. PAOLO BALDAN e MICHELE SCQUIZZATO

    Varie informazioni sul corso (quali riferimenti bibliografici e modalità d'esame) si possono trovare alla pagina del corso. Qui verrà tenuto un diario del corso e saranno inserite informazioni addizionali (es. esercizi assegnati e soluzioni). Inoltre il forum sarà utilizzato per comunicazioni riguardanti il corso. Una raccolta di esercizi con bozze di soluzioni è disponibile a questo link. Se preferite una versione senza soluzioni, la trovate a questo link.

    La descrizione degli argomenti trattati riporta un riferimento alle parti del libro corrispondenti nella forma "§...".

    Le lezioni si tengono in presenza.

  • 3 October - 9 October

    • (Lezione 1)
      • Introduzione al corso. 
      • Problem solving e algoritmi. 
      • Analisi e progettazione (§1). Insertion sort (§2.1).
    • (Lezione 2) 
      • Analisi di insertion sort (§2.2). 
      • Divide et impera. Mergesort (§2.3)
    • (Lezione 3) 
      • Mergesort: Analisi e confronto con Insertion Sort (§2.3).

    Esercizi Assegnati:

    • (InsertionSort Ricorsivo) Realizzare una versione ricorsiva della funzione InsertionSort.
    • (Duplicati) Realizzare una funzione Dup(A,p,r) che verifica, in modo divide et impera, la presenza di duplicati nell'array A, restituendo un booleano. Estenderla ad una funzione DupCount(A,p,r) che conti il numero di duplicati, ovvero il numero di coppie \( \{ (i,j)  \mid  i \neq j\ \land\  A[i]=A[j] \} \)
      (Può essere interessante anche considerare varianti in cui si contano i valori ripetuti ovvero \( \{ A[i] \mid  \exists j.\ j \neq i. A[i]=A[j] \} \) o gli indici corrispondenti a ripetizioni ovvero \( \{ i \mid \exists j.\ j \neq i. A[i]=A[j] \} \).)
    • (Sum) Realizzare una funzione Sum(A,key) che dato un array A e un intero key verifica se questo è esprimibile come la somma di due elementi di A ovvero se vi sono indici tali che key = A[i] + A[j].
  • 10 October - 16 October

    • (Lezione 4)
      • Confronto di algoritmi: Notazione Asintotica. Metodo del Limite (§3.1). 
    • (Lezione 5) 
      • Complessità dei problemi. Limite inferiore per l'ordinamento basato su scambi di elementi contigui.
      • Ricorrenze. Metodo di sostituzione. (§4.3)
    • (Lezione 6) 
      • Soluzione di ricorrenze: Master theorem (§4.5)

    Esercizi Assegnati (Lezione 4)

    Dimostrare le seguenti uguaglianze:

    • \(f(n) = O(g(n))\) sse \(g(n) = \Omega(f(n))\)
    • \(\Theta(g(n)) = O(g(n)) \cap \Omega(g(n))\)
    • \(f(n) = \Theta(f(n))\)
    • \(f(n) = \Theta(g(n))\) sse \(\Theta(f(n)) = \Theta(g(n))\) sse \(g(n) = \Theta(f(n))\)
    • \(f(n) = O(g(n))\) e \(g(n) = O(h(n))\) implica \(f(n) = O(h(n))\)

    Esercizi Assegnati (Lezione 5)

    Risolvere con il metodo di sostituzione le seguenti ricorrenze (la soluzione è sviluppata in dettaglio nelle note PDF associate alla lezione):

    • La ricorrenza \( T(n) = 2 T(n/2) + \Theta(n)\) ha soluzione \(T(n) =\Theta(n \log n)\) 
    • La ricorrenza \( T(n) = T(n/3) + T(2n/3) + \Theta(n)\) ha soluzione \(T(n) =\Theta(n \log n)\)

  • 17 October - 23 October

    • (Lezione 7)
      • Soluzione ad alcuni esercizi assegnati in precedenza (si veda il testo sotto)
    • (Lezione 8)
      • HeapSort: struttura heap (§6.1)
      • Mantenimento della proprietà di heap (§6.2)
    • (Lezione 9)
      • Costruzione di un max-heap (§6.3), 
      • Heapsort (§6.4)
      • Code di priorità (§6.5)


    Esercizi assegnati

    • (Mergesort Allocazione Singola) Realizzare una versione del mergesort nella quale l'array di supporto è allocato staticamente (quindi la procedura sarà del tipo MergeSort(A,B, ...) dove A è l'array di input, mentre B un array della stessa dimensione utilizzato per la memorizzazione temporanea
      • Versione 1: l'array B è utilizzato per memorizzare temporaneamente le parti di array già ordinate delle quali si deve effettuare il merge
      • Versione 2: la procedura Merge fa alternativamente il merge dei sottoarray già ordinati da A verso B e vice versa, di modo da evitare la fase di copia dei sottoarray dei quali fare il merge.


    Soluzione esercizi assegnati in precedenza

    • (InsertionSort Ricorsivo) Realizzare una versione ricorsiva della funzione InsertionSort.
      [Soluzione]

    • (Duplicati) Realizzare una funzione Dup(A,p,r) che verifica, in modo divide et impera, la presenza di duplicati nell'array A, restituendo un booleano. Estenderla ad una funzione DupCount(A,p,r) che conti il numero di duplicati, ovvero il numero di coppie \( \{ (i,j)  \mid  i \neq j\ \land\  A[i]=A[j] \} \)
      (Può essere interessante anche considerare varianti in cui si contano i valori ripetuti ovvero \( \{ A[i] \mid  \exists j.\ j \neq i. A[i]=A[j] \} \) o gli indici corrispondenti a ripetizioni ovvero \( \{ i \mid \exists j.\ j \neq i. A[i]=A[j] \} \).)
      [Soluzione]

    • (Sum) Realizzare una funzione Sum(A,key) che dato un array A e un intero key verifica se questo è esprimibile come la somma di due elementi di A ovvero se vi sono indici tali che key = A[i] + A[j].
      [Soluzione]
  • 24 October - 30 October

    • (Lezione 10)
      • Quicksort: Descrizione (§7.1) e prestazioni (§7.2). 
    • (Lezione 11)
      • Quicksort: cenni al caso medio
      • Versione Randomizzata (§7.3) e al caso medio 
      • Tripartizione (esercizio, si veda sotto)
      • Limite inferiore per l'ordinamento basato su confronti (§8.1)

    • (Lezione 12)
      • Soluzione di esercizi assegnati in precedenza (si veda sotto)

    Esercizi risolti

    • (Limiti Asintotici - BaseDimostrare le seguenti uguaglianze:
      • \( f(n) = O(g(n)) \) sse \( g(n) = \Omega(f(n)) \)
      • \( \Theta(g(n)) = O(g(n)) \cap \Omega(g(n)) \)
      • \( f(n) = \Theta(f(n)) \)
      • \( f(n) = O(g(n)) \) e \( g(n) = O(h(n)) \) implica \( f(n) = O(h(n)) \)

        [soluzione]

    •  (Limiti Asintotici - Ricorrenze) Risolvere le seguenti ricorrenze:
      • \( T(n) = 2 T(n/2) + \log(n) \)
      • \( T(n) = 2 T(n/2) + n^2 \)
      • \( T(n) = 2 T(n/2) + n \log(n) \)

        [soluzione]

    • (Mergesort Allocazione Singola) Realizzare una versione del mergesort nella quale l'array di supporto è allocato staticamente (quindi la procedura sarà del tipo MergeSort(A,B, ...) dove è l'array di input, mentre  B un array della stessa dimensione utilizzato per la memorizzazione temporanea
      • Versione 1: l'array B è utilizzato per memorizzare temporaneamente le parti di array già ordinate delle quali si deve effettuare il merge
      • Versione 2: la procedura Merge fa alternativamente il merge dei sottoarray già ordinati da A verso B e vice versa, di modo da evitare la fase di copia dei sottoarray dei quali fare il merge.

        [soluzione]

    • (Tripartition) Realizzare una versione del quick sort QuickSort(A,p,r) che si basi su di una tripartizione degli elementi, ovvero Partition(A,p,r) divide gli elementi in quelli minori della chiave, quelli uguali e quelli maggiori. Concretamente ritorna una coppia di indici q1q2 che individuano le tre partizioni in oggetto come A[p..q1-1]A[q1..q2] e A[q2+1..r]

      [soluzione]



    Esercizi Assegnati


    • (Monete) Siano date \(n\) monete, delle quali una è falsa. Le monete sono identiche esteticamente, ma quella falsa pesa meno delle altre. Data una bilancia a due piatti e avendo a disposizione come operazioni solo la pesata di due sottoinsiemi (disgiunti) di monete, dare un algoritmo di complessità \( O(\log n) \) che determina qual'è la moneta falsa. Mostrare che questa è la complessità del problema, ovvero che ogni algoritmo è \( \Omega(\log n) \)

    • (Select) Realizzare una funzione Select(A, k) che restituisce l'elemento che occuperebbe la k-ma posizione nell'array A ordinato. Detta n la dimensionedell'array, trovare soluzioni:
      • \( O(n \log(n)) \)
      • \( O(n + k \log(n)) \)
      • \( O(n \log(k)) \)
          Per gli ultimi due casi il suggerimento è quello di usare un MinHeap e un MaxHeap rispettivamente.

    • (Inversioni) Realizzare con approccio divide et impera una funzione Inv(A,p,r)che ritorna il numero di inversioni in A[p,r], ovvero il numero di coppie di indici i, j tali che i < j e A[i] > A[j] [Suggerimento: Modificare il MergeSort]

    • (Linked Heaps) Fornire una implementazione dei max-heap come alberi realizzati mediante strutture a puntatori, ovvero ogni nodo x avrà (almeno) i campi x.key che contiene la chiave, x.left che riferisce il figlio sinistro, x.right che riferisce il figlio destro. Lo heap sarà poi una struttura che contiene un riferimento alla radice e possibilmente altre informazioni. Realizzare le varie operazioni studiate sugli heap e valutarne la complessità.

    • (Fusione di Heap) Realizzare una procedura Fusion(T1,T2) per fondere due alberi binari T1 e T2, il primo completo, il secondo quasi completo, della stessa altezza, che soddisfano la proprietà di Max-Heap, mantenendo questa proprietà. Cercare una soluzione di costo \( O(\log(n)) \) dove n è il numero di elementi totali dei due alberi.


  • 31 October - 6 November

    • (Lezione 13)
      • Ordinamento in tempo lineare: Counting Sort (§8.2) e Radix Sort (§8.3)
  • 7 November - 13 November

    • (Lezione 14)
      • Tabelle Hash: Intro (§11.1),  Chaining (§11.2) e Hash functions (§11.3)
    • (Lezione 15)
      • Tabelle Hash:  Open addressing (§11.4)
    • (Lezione 16)
      • Soluzione esercizi assegnati in precedenza (Monete, Select, Inversioni, Linked Heaps, Fusione di Heap) - si veda sotto


    Esercizi Risolti

    • (Monete) Siano date \(n\) monete, delle quali una è falsa. Le monete sono identiche esteticamente, ma quella falsa pesa meno delle altre. Data una bilancia a due piatti e avendo a disposizione come operazioni solo la pesata di due sottoinsiemi (disgiunti) di monete, dare un algoritmo di complessità \( O(\log n) \) che determina qual'è la moneta falsa. Mostrare che questa è la complessità del problema, ovvero che ogni algoritmo è \( \Omega(\log n) \)
      [soluzione]

    • (Select) Realizzare una funzione Select(A, k) che restituisce l'elemento che occuperebbe la k-ma posizione nell'array A ordinato. Detta n la dimensionedell'array, trovare soluzioni:
      • \( O(n \log(n)) \)
      • \( O(n + k \log(n)) \)
      • \( O(n \log(k)) \)
          Per gli ultimi due casi il suggerimento è quello di usare un MinHeap e un MaxHeap rispettivamente.
          [soluzione]

    • (Inversioni) Realizzare con approccio divide et impera una funzione Inv(A,p,r)che ritorna il numero di inversioni in A[p,r], ovvero il numero di coppie di indici i, j tali che i < j e A[i] > A[j] [Suggerimento: Modificare il MergeSort]
      [soluzione]

    • (Linked Heaps) Fornire una implementazione dei max-heap come alberi realizzati mediante strutture a puntatori, ovvero ogni nodo x avrà (almeno) i campi x.key che contiene la chiave, x.left che riferisce il figlio sinistro, x.right che riferisce il figlio destro. Lo heap sarà poi una struttura che contiene un riferimento alla radice e possibilmente altre informazioni. Realizzare le varie operazioni studiate sugli heap e valutarne la complessità.
      [soluzione]

    • (Fusione di Heap) Realizzare una procedura Fusion(T1,T2) per fondere due alberi binari T1 e T2, il primo completo, il secondo quasi completo, della stessa altezza, che soddisfano la proprietà di Max-Heap, mantenendo questa proprietà. Cercare una soluzione di costo \( O(\log(n)) \) dove n è il numero di elementi totali dei due alberi.
      [soluzione]

    Esercizi assegnati

    • (Anagramma) Mostrare che la funzione di hash \( h(k) = k \mathop{mod} m \), quando \( m= 2^p-1 \) e le chiavi \(k\) consistono di \(w\) parole di \(p\) bit è invariante rispetto a permutazioni delle parole costituenti la chiave.

  • 14 November - 20 November

    • (Lezione 17)
      • Alberi Binari di ricerca: Definizione, Elenco ordinato degli elementi (§12.1), Ricerca, Minimo, Massimo, Predecessore, Successore (§12.2),  Inserimento (§12.3)
    • (Lezione 18)
      • Alberi Binari di ricerca: Cancellazione (§12.3)
      • Red-Black Trees: Definizione e proprietà (§13.1)
    • (Lezione 19)
      • Red-black trees: rotazioni (§13.2), inserimento (§13.3) e cancellazione (cenni, §13.4)

    Esercizi assegnati

    • (ABR-InOrder) Dimostrare che un albero binario è un Albero Binario di Ricerca se e solo se una visita simmetrica elenca i nodi in ordine di chiave crescente.
    • (Max-Heap Ordinato) Dire se esiste un algoritmo di tempo lineare per elencare gli elementi di un max-heap in ordine crescente o decrescente. Descrivere l'algoritmo oppure motivare l'impossibilità di realizzarlo.
    • (ABR lineare) Dire se esiste un algoritmo di tempo lineare per costruire un Albero Binario di Ricerca che sia quasi completo, a partire da un array A. Descrivere l'algoritmo oppure motivare l'impossibilità di realizzarlo.
    • (ABR insert ricorsiva) Realizzare una versione ricorsiva della procedura Insert(T,x) per gli alberi binari di ricerca.
    • (ABR con successore) Realizzare una implementazione degli alberi binari di ricerca nella quale il campo p (padre) è sostituito dal campo succ (successore).

  • 21 November - 27 November

    • (Lezione 20)
      • Introduzione alla programmazione dinamica: critica al D&C, e memoizzazione (§15.3)
    • (Lezione 21) Soluzione di esercizi assegnati in precedenza (si veda sotto)


    Soluzione degli esercizi assegnati

    • (Anagramma) Mostrare che la funzione di hash \( h(k) = k \mathop{mod} m \), quando \( m= 2^p-1 \) e le chiavi \(k\) consistono di \(w\) parole di \(p\) bit è invariante rispetto a permutazioni delle parole costituenti la chiave.
      [soluzione]

    • (ABR-InOrder) Dimostrare che un albero binario è un Albero Binario di Ricerca se e solo se una visita simmetrica elenca i nodi in ordine di chiave crescente.
      [soluzione]

    • (Max-Heap Ordinato) Dire se esiste un algoritmo di tempo lineare per elencare gli elementi di un max-heap in ordine crescente o decrescente. Descrivere l'algoritmo oppure motivare l'impossibilità di realizzarlo.
      [soluzione]

    • (ABR lineare) Dire se esiste un algoritmo di tempo lineare per costruire un Albero Binario di Ricerca che sia quasi completo, a partire da un array A. Descrivere l'algoritmo oppure motivare l'impossibilità di realizzarlo.
      [soluzione]

    • (ABR insert ricorsiva) Realizzare una versione ricorsiva della procedura Insert(T,x) per gli alberi binari di ricerca.
      [soluzione]

    • (ABR con successore) Realizzare una implementazione degli alberi binari di ricerca nella quale il campo p (padre) è sostituito dal campo succ (successore).
      [soluzione]

  • 28 November - 4 December

    • (Lezione 23)
      • Problemi di ottimizzazione, paradigma generale, definizioni su stringhe (§15.3)
    • (Lezione 24) 
      • Longest Common Subsequence (LCS): definizione, proprieta' di sottostruttura ottima e dimostrazione (§15.4)
    • (Lezione 25)
      • LCS: ricorsione sui costi e codice bottom-up (§15.4)

  • This week

    5 December - 11 December

    • (Lezione 26)
      • LCS: esempi, codice memoizzato e analisi al caso migliore, considerazioni sulla complessita' in spazio (§15.4)
    • (Lezione 27) 
      • Esercizi di programmazione dinamica (Esercizio 21 della raccolta di esercizi)

    Esercizi:
    • Calcolare la LCS tra spanking e amputation (calcolare solo la tabella L[i,j] delle lunghezze) [soluzione]
    • Esercizi 18 e 20 nella raccolta di esercizi