DiarioLezioni < Intro_algo/EO

Tags: view all tags
---++Diario delle lezioni (Introduzione agli Algoritmi, secondo canale, A.A. 2014-2015)

<font color="#AF0F0F"><b>Lunedì 23 Febbraio (2h)</b></font> - Introduzione al corso. Administrivia. Cosa è un algoritmo (primo esempio: l'algoritmo per il calcolo del voto). Correttezza ed efficienza. Perché è importante progettare algoritmi efficienti: ordinare 1GB di dati eseguendo n<sup>2</sup> oppure n log n confronti, alcune considerazioni pratiche. Come si misura il tempo di esecuzione? Analisi del numero di linee di codice/numero di operazioni elementari eseguite da semplici programmi iterativi con cicli:

<table border="0">
   <tr>
      <td><PRE>
     Algoritmo 1 (int n)
      i=1
      while (i<=n) do i++
     </PRE></td>
     
     <td><PRE>
     Algoritmo 2 (int n) 
      i=0
      while (i<=n) do i=i+3
     </PRE></td>      
  </tr>
</table> 

<font color="#AF0F0F"><b>Giovedì 26 Febbraio (3h)</b></font> - Da n a log n (cambiando un solo carattere!):

<table border="0">
   <tr>
     <td><PRE>
     Algoritmo 3 (int n) 
      i=1
      while (i<=n) do i=i+i
     </PRE></td>
  </tr>
</table> 
Analisi del numero di linee di codice eseguite da semplici programmi iterativi con cicli nidificati:

<table border="0">
   <tr>
      <td><PRE>
     Algoritmo 4 (int n) -> int 
      count=0
      i=1
      while (i<=n) do
         for j=1 to n
             count++
         i++
      return count
     </PRE></td>
     
     <td><PRE>
     Algoritmo 5 (int n) -> int 
      count=0
      i=1
      while (i<=n) do
         for j=1 to i
             count++
         i++
      return count
     </PRE></td>

     <td><PRE>
     Algoritmo 6 (int n) -> int 
     count=0
     x = n
     while (x>=1) do
         for j=1 to x
             count++
         x=x/2
     return count
     </PRE></td> </tr>
</table> 
Variazioni sul tema. Serie aritmetica e serie geometrica di ragione 1/2 (con dimostrazione).  Concetto di operazione dominante.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (A)</B> 

_Esercizio A1._ Quante volte viene stampato "Hello world" da ciascuno dei seguenti programmi?
<table border="0">
   <tr>
      <td><PRE>
     i=1
     if (n>5) i=n-5;
     while (i<=n) do 
       print "Hello world"
       i=i+1
     </PRE></td>
     
      <td><PRE>
     i=27
     while (i<=n) do 
       print "Hello world"
       i=i*3
     </PRE></td>
     
     <td><PRE>
     for i=1 to n
       for j=1 to i
         for k=1 to j
           print "Hello world"
     </PRE></td>

     <td><PRE>
     for i=1 to n
       for j=1 to i
         print "Hello world"
       for k=5 to 2i
         print "Hello world"
     </PRE></td>    

     <td><PRE>
     count=0
     x = n
     while (x>=1) do
         for j=1 to n
             print "Hello world"
         x=x/2
     return count
     </PRE></td> 
  </tr>
  <tr>
     <td align="center"><b>(A1.1)</b></td>
     <td align="center"><b>(A1.2)</b></td>    
     <td align="center"><b>(A1.3)</b></td>    
     <td align="center"><b>(A1.4)</b></td>    
     <td align="center"><b>(A1.5)</b></td>    
  </tr>
</table>

_Esercizio A2._ Quanto sono grandi le istanze di input gestibili in 24h da un algoritmo con tempo di esecuzione n, n<sup>2</sup>, 2<sup>n</sup> assumendo che una operazione elementare richieda un millisecondo? E se la CPU diventasse 10 volte più veloce? Quale dei tre algoritmi ne beneficerebbe di più?
</BLOCKQUOTE>


<font color="#AF0F0F"><b>Lunedì 2 Marzo (2h)</b></font> -  Introduzione alla notazione asintotica O, Omega, Theta. Limitazione stretta. Esempi di confronto tra funzioni applicando le definizioni e usando l'algebra elementare. Caratterizzazione dell'asintotica di un polinomio generico. Relazioni tra limite del rapporto e confronto tra funzioni. 

<font color="#AF0F0F"><b>Giovedì 5 Marzo (3h)</b></font> - Introduzione all'analisi di algoritmi ricorsivi. Il problema dei conigli di Fibonacci: l'albero dei conigli, _F<sub>n</sub>=F<sub>n-1</sub>+F<sub>n-2</sub>_, sezione aurea. Un algoritmo numerico non corretto. Algoritmo ricorsivo. Call stack, record di attivazione, albero delle chiamate ricorsive (call tree). Dalla call stack (visione istantanea dell'esecuzione) al call tree (visione storica). Impostazione equazione di ricorrenza. Relazione tra call tree ed equazione di ricorrenza.

<font color="#AF0F0F"><b>Lunedì 9 Marzo (2h)</b></font> - Dimostrazione delle relazioni tra limite del rapporto e relazione asintotica tra due funzioni. Criterio del rapporto. Classi di funzioni principali: logaritmica, polinomiale, esponenziale, fattoriale. Dimostrazione delle separazioni tra le classi. 

<font color="#AF0F0F"><b>Giovedì 12 Marzo (3h)</b></font> - Analisi del tempo di esecuzione dell'algoritmo ricorsivo per il calcolo dei numeri di Fibonacci. Algoritmo iterativo.

<font color="#AF0F0F"><b>Lunedì 16 Marzo (2h)</b></font> - Analisi in funzione della dimensione dell'input. Caso peggiore, migliore e medio. Delimitazioni superiori e inferiori alle risorse di calcolo richieste da uno specifico algoritmo o per risolvere un certo problema. Bubblesort.

<font color="#AF0F0F"><b>Giovedì 19 Marzo (3h)</b></font> - Ordinamenti incrementali: selectionSort e insertionSort. Analisi correttezza e tempi di esecuzione. Esercizi presi da prove d'esame.

<font color="#AF0F0F"><b>Lunedì 23 Marzo (2h)</b></font> - Equazioni di ricorrenza

<font color="#AF0F0F"><b>Giovedì 26 Marzo (3h)</b></font> - Mergesort. Ricerca binaria. Equazioni di ricorrenza: analisi dell'albero della ricorsione e svolgimento della ricorrenza per iterazione. Problema 4.12 del libro di testo. 

<BLOCKQUOTE>
<B>Esercizi di riepilogo (B)</B> 

_Dal libro di testo:_ Problema 4.13. Esercizi 4.7 e 4.12

_Da prove d'esame:_ 12 giugno 2012 (es. 2 e 3), 7 febbraio 2013 (es. 2), 24 aprile 2012 (es. 1, 2 e 3)
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Lunedì 30 Marzo (2h)</b></font> - Quicksort, partition in loco, analisi nel caso peggiore, intuizione nel caso medio. Ricorrenze: a) T(n) = T(n-1) + n; b) T(n) = T(n/4) + T(3n/4) + n.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (C): preparazione all'esonero</B> 

_Prove d'esame._ 16 aprile 2013 (tutti), 26 aprile 2012 (testo 1, tutti gli esercizi), 28 aprile 2011 (tutti), 29 aprile 2010 (es. 1, 2 e 3). 

_Dal libro di testo._ Problemi 1.1, 1.2, 1.3, 1.4, 2.2, 2.3, 2.4, 2.9, 2.10, 4.7.

_Esercizio C1._ Il Professor Bifolcacci sostiene di saper sfruttare la relazione di ricorrenza che definisce i numeri di Fibonacci per ottenere un algoritmo ricorsivo con tempo di esecuzione subesponenziale. In particolare, l'algoritmo del Professor Bifolcacci  prima calcola ricorsivamente F<sub>n-2</sub> e F<sub>n-3</sub>, e poi restituisce F<sub>n</sub>=2F<sub>n-2</sub>+F<sub>n-3</sub>. 
   * Dimostrate che l'algoritmo è corretto (usate la definizione di numeri di Fibonacci).
   * Disegnate l'albero della ricorsione per n=10.
   * Impostate una relazione di ricorrenza per il tempo di esecuzione.
   * [Diff] Dimostrate che il professore ha commesso un errore: il tempo di esecuzione è ancora esponenziale! E' sufficiente dare una minorazione al tempo di esecuzione, ovvero far vedere che il tempo di esecuzione _T(n)&ge;g(n)_, dove _g(n)_ è una opportuna funzione con crescita esponenziale.

_Esercizio C2._ Considerate il famoso gioco delle [[http://en.wikipedia.org/wiki/Tower_of_Hanoi][torri di Hanoi]]. 
   * Progettate un algoritmo ricorsivo che risolva il problema con n dischi e 3 torri.
   * Impostate una relazione di ricorrenza per il numero di spostamenti di dischi eseguiti dall'algoritmo.
   * Disegnate l'albero della ricorsione per n=5.
   * [Diff] Analizzando l'albero, dimostrate che il numero di spostamenti effettuati è _2<sup>n</sup>-1_. Suggerimento: dopo aver capito come etichettare ciascun nodo, calcolate il numero di nodi dell'albero sommando i numeri di nodi che si trovano su ciascun livello (dovete ottenere una serie geometrica).

_Esercizio C3._ Progettare ed analizzare un algoritmo iterativo ed un algoritmo ricorsivo per risolvere il seguente problema: dati due vettori A e B, entrambi di dimensione n, calcolare il prodotto scalare A x B. Il prodotto A x B è definito come la somma dei prodotti A[i] x B[i], dove A[i] è il valore dell'i-esima coordinata di A e B[i] è il valore dell'i-esima coordinata di B. Analizzare il tempo di esecuzione degli algoritmi proposti.

_Esercizio C4._ Progettare ed analizzare un algoritmo che, date due matrici quadrate A e B, entrambe di lato n, calcoli la matrice prodotto A x B. Qual è il tempo di esecuzione dell'algoritmo proposto in funzione di n? Generalizzare l'algoritmo assumendo che A abbia dimensione n x k e B abbia dimensione k x m. Calcolare inoltre il tempo di esecuzione T(n,k,m) come una funzione di n, k ed m.

</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Giovedì 2 Aprile (3h)</b></font> - vacanze di Pasqua

<font color="#AF0F0F"><b>Lunedì 6 Aprile (2h)</b></font> - vacanze di Pasqua

<font color="#AF0F0F"><b>Giovedì 9 Aprile (3h)</b></font> - Esercizi in preparazione dell'esonero: es. 1 del 27/09/2011, es. 1.1 del 14/07/2009, es. 1.2 del 14/07/2009, es. 1 del 23 Aprile 2009, es. 1 del 20/09/2010, problema 2 16/04/2013, problema 2 26/04/2012, es. 2 del 29/04/2010 

<font color="#AF0F0F"><b>Lunedì 13 Aprile (2h)</b></font> - interruzione didattica per svolgimento prove intermedie

<font color="#AF0F0F"><b>Martedì 14 Aprile</b></font> - *prova intermedia*, *data da confermare*.

<font color="#AF0F0F"><b>Giovedì 16 Aprile (3h)</b></font> - interruzione didattica per svolgimento prove intermedie

 <font color="#AF0F0F"><b>Lunedì 20 Aprile (2h)</b></font> - Heap binari, proprietà, calcolo dell'altezza, cancellazione del massimo, procedure !fixHeap, vettore posizionale.

<font color="#AF0F0F"><b>Giovedì 23 Aprile (3h)</b></font> - Costruzione di un heap binario: (1) tramite inserimenti ripetuti; (2) in tempo lineare tramite algoritmo heapify Teorema master: enunciato, esempi, intuizione sulla funzione n<sup>log<sub>b</sub>a</sup>.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (D)</B> 

_Dal libro di testo:_ esercizi 4.3, 4.4, 4.5. Problemi 4.4 e 4.5.

_Da prove d'esame:_ es. 3 del 4 giugno 2013, es. 4 del 23 gennaio 2012, es. 5 del 12 giugno 2012, es. 3 del 20 giugno 2011 (parti a e b), es. 3 del 21 luglio 2010, es. 2 del 15 settembre 2009.
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Lunedì 27 Aprile (2h)</b></font> - Correzione esercizi prova intermedia.

<font color="#AF0F0F"><b>Giovedì 30 Aprile (3h)</b></font> - Lower bound al tempo di esecuzione di algoritmi di ordinamento basati su confronti. Counting sort: ordinare interi (piccoli) in tempo lineare.

<font color="#AF0F0F"><b>Lunedì 4 Maggio (2h)</b></font> - Correzione esercizi prova intermedia.

<font color="#AF0F0F"><b>Giovedì 7 Maggio (3h)</b></font> - Alberi: rappresentazioni collegate e indicizzate. Visite di alberi: generica, in ampiezza e in profondità.

<font color="#AF0F0F"><b>Lunedì 11 Maggio (2h)</b></font> - Visione e discussione esoneri. Introduzione ai dizionari: implementazioni banali.

<font color="#AF0F0F"><b>Giovedì 14 Maggio (3h)</b></font> - Alberi binari di ricerca. Alberi AVL. Fattore di bilanciamento. Alberi di Fibonacci. Dimostrazione altezza logaritmica.

<font color="#AF0F0F"><b>Lunedì 18 Maggio (2h)</b></font> - 

<font color="#AF0F0F"><b>Giovedì 21 Maggio (3h)</b></font> - Rotazioni, classificazione e proprietà. Inserimento e cancellazione in alberi AVL.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (E)</B> 

_Dal libro di testo:_ esercizi 6.1, 6.2, 6.3, 6.4, 6.5, 6.6. Problemi 6.3, 6.4, 6.5, 6.6.

_Da prove d'esame:_ . es. 3 e 4 del 23 gennaio 2014; es. 3, 4 e 5 del 4 giugno 2013; es. 4, 5 e 6 del 12 giugno 2012;  es. 3 e 4 del 20 giugno 2011.
</BLOCKQUOTE>


<font color="#AF0F0F"><b>Lunedì 25 Maggio (2h)</b></font> - 

<font color="#AF0F0F"><b>Giovedì 28 Maggio (3h)</b></font> - 







<!--
<font color="#AF0F0F"><b>Giovedì 6 Marzo (3h)</b></font> - Introduzione al corso. Administrivia. Cosa è un algoritmo. Correttezza ed efficienza. Perché è importante progettare algoritmi efficienti: ordinare 1GB di dati eseguendo n<sup>2</sup> oppure n log n confronti, alcune considerazioni pratiche. Come si misura il tempo di esecuzione? Analisi del numero di linee di codice/numero di operazioni elementari eseguite da semplici programmi iterativi con cicli:

<table border="0">
   <tr>
      <td><PRE>
     Algoritmo 1 (int n)
      i=1
      while (i<=n) do i++
     </PRE></td>
     
     <td><PRE>
     Algoritmo 2 (int n) 
      i=0
      while (i<=n) do i=i+3
     </PRE></td>
      
     <td><PRE>
     Algoritmo 3 (int n) 
      i=1
      while (i<=n) do i=i+i
     </PRE></td>
  </tr>
</table> 
Introduzione alla notazione asintotica &Theta; e primi esempi.

<font color="#AF0F0F"><b>Lunedì 10 Marzo (2h)</b></font> - Analisi del numero di linee di codice eseguite da semplici programmi iterativi con cicli nidificati:

<table border="0">
   <tr>
      <td><PRE>
     Algoritmo 4 (int n) -> int 
      count=0
      i=1
      while (i<=n) do
         for j=1 to n
             count++
         i++
      return count
     </PRE></td>
     
     <td><PRE>
     Algoritmo 5 (int n) -> int 
      count=0
      i=1
      while (i<=n) do
         for j=1 to i
             count++
         i++
      return count
     </PRE></td>

     <td><PRE>
     Algoritmo 6 (int n) -> int 
     count=0
     x = n
     while (x>=1) do
         for j=1 to x
             count++
         x=x/2
     return count
     </PRE></td> </tr>
</table> 
Variazioni sul tema con cicli sequenziali e chiamate a subroutine. Serie aritmetica e serie geometrica di ragione 1/2 (con dimostrazione).  Concetto di operazione dominante.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (B)</B> 

_Dal libro di testo:_ Problema 4.13. Esercizi 4.7 e 4.12

_Da prove d'esame:_ 12 giugno 2012 (es. 2 e 3), 7 febbraio 2013 (es. 2), 24 aprile 2012 (es. 1, 2 e 3)
</BLOCKQUOTE>

<font color="#AF0F0F"><b>Giovedì 13 Marzo (3h)</b></font> - Introduzione all'analisi di algoritmi ricorsivi. Il problema dei conigli di Fibonacci: l'albero dei conigli, _F<sub>n</sub>=F<sub>n-1</sub>+F<sub>n-2</sub>_, sezione aurea, crescita esponenziale. Un algoritmo numerico non corretto. Algoritmo ricorsivo. Albero delle chiamate ricorsive (call tree). Analisi dell'algoritmo ricorsivo per il calcolo di _F<sub>n</sub>_: calcolo del numero di linee di codice eseguite tramite analisi del call tree, proprietà del call tree (numero di foglie, numero di nodi interni), impostazione equazione di ricorrenza. Soluzione esercizi A1.2 e A1.5.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (B).</B> 

_Esercizio B1._ Il Professor Bifolcacci sostiene di saper sfruttare la relazione di ricorrenza che definisce i numeri di Fibonacci per ottenere un algoritmo ricorsivo con tempo di esecuzione subesponenziale. In particolare, l'algoritmo del Professor Bifolcacci  prima calcola ricorsivamente F<sub>n-2</sub> e F<sub>n-3</sub>, e poi restituisce F<sub>n</sub>=2F<sub>n-2</sub>+F<sub>n-3</sub>. 
   * Dimostrate che l'algoritmo è corretto (usate la definizione di numeri di Fibonacci).
   * Disegnate l'albero della ricorsione per n=10.
   * Impostate una relazione di ricorrenza per il tempo di esecuzione.
   * [Diff] Dimostrate che il professore ha commesso un errore: il tempo di esecuzione è ancora esponenziale! E' sufficiente dare una minorazione al tempo di esecuzione, ovvero far vedere che il tempo di esecuzione _T(n)&ge;g(n)_, dove _g(n)_ è una opportuna funzione con crescita esponenziale.

_Esercizio B2._ Considerate il famoso gioco delle [[http://en.wikipedia.org/wiki/Tower_of_Hanoi][torri di Hanoi]]. 
   * Progettate un algoritmo ricorsivo che risolva il problema con n dischi e 3 torri.
   * Impostate una relazione di ricorrenza per il numero di spostamenti di dischi eseguiti dall'algoritmo.
   * Disegnate l'albero della ricorsione per n=5.
   * [Diff] Analizzando l'albero, dimostrate che il numero di spostamenti effettuati è _2<sup>n</sup>-1_. Suggerimento: dopo aver capito come etichettare ciascun nodo, calcolate il numero di nodi dell'albero sommando i numeri di nodi che si trovano su ciascun livello (dovete ottenere una serie geometrica).

_Esercizio B3._ Svolgete i problemi 1.1, 1.2, 1.3 (tranne parte c) dal libro di testo.
</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Lunedì 17 Marzo (2h)</b></font> - Due algoritmi iterativi con tempo lineare, analisi della quantità di memoria richiesta. Un algoritmo logaritmico per il calcolo di _F<sub>n</sub>_: numeri di Fibonacci e potenze di matrice. Esponenziazione di interi tramite il metodo dei quadrati ripetuti: algoritmo per il calcolo della n-esima potenza di un numero in tempo _&Theta;(log n)_, analisi dell'albero della ricorsione, impostazione dell'equazione di ricorrenza. 

<BLOCKQUOTE>
<B>Esercizi di riepilogo (C).</B> 

_Esercizio C1._ Sia Fib un array di n interi, inizializzati tutti a 0. Progettate un algoritmo che memorizzi in Fib[i] l'i-esimo numero di Fibonacci F<sub>i</sub>, per ogni i in [1,n]. L'algoritmo, a partire dal calcolo di F<sub>n</sub>, deve operare ricorsivamente secondo la seguente strategia: a) se i=1 o i=2, pone Fib[i]=1 ed esce; b) se Fib[i-1]=0, calcola Fib[i-1] ricorsivamente; c) se Fib[i-2]=0, calcola Fib[i-2] ricorsivamente; d) memorizza in Fib[i] la somma Fib[i-1]+Fib[i-2] ed esce.
   * Date lo pseudocodice dell'algoritmo
   * Disegnate l'albero della ricorsione per il calcolo di F<sub>6</sub>
   * Analizzate il tempo di esecuzione dell'algoritmo
   * Ripetete i punti precedenti assumendo che i passi b) e c) siano invertiti

_Esercizio C2._ Progettare ed analizzare un algoritmo iterativo ed un algoritmo ricorsivo per risolvere il seguente problema: dati due vettori A e B, entrambi di dimensione n, calcolare il prodotto scalare A x B. Il prodotto A x B è definito come la somma dei prodotti A[i] x B[i], dove A[i] è il valore dell'i-esima coordinata di A e B[i] è il valore dell'i-esima coordinata di B. Analizzare il tempo di esecuzione degli algoritmi proposti.

_Esercizio C3._ Progettare ed analizzare un algoritmo che, date due matrici quadrate A e B, entrambe di lato n, calcoli la matrice prodotto A x B. Qual è il tempo di esecuzione dell'algoritmo proposto in funzione di n? Generalizzare l'algoritmo assumendo che A abbia dimensione n x k e B abbia dimensione k x m. Calcolare inoltre il tempo di esecuzione T(n,k,m) come una funzione di n, k ed m.

_Esercizio C4._ Risolvere l'esercizio 1 dell'appello del 23 gennaio 2014

_Esercizio C5._ Risolvere l'esercizio 1 dell'appello del 24 aprile 2012

_Esercizio C6._ Risolvere l'esercizio 2 dell'appello del 3 luglio 2012
</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Giovedì 20 Marzo (3h)</b></font> - Notazioni asintotiche &Theta;(g(n)), O(g(n)), &Omega;(g(n)). Proprietà di base delle notazioni asintotiche:<ul>
<li>
f(n)=&Theta;(g(n)) se e solo se f(n)=O(g(n)) e f(n)=&Omega;(g(n)) 
</li>
<li>
Proprietà transitiva, riflessiva, simmetrica: per quali notazioni asintotiche valgono?
</li>
<li>
Proprietà di simmetria trasposta.
</li>
</ul>
Esempi. Metodo algebrico ed analitico. Proprietà dei polinomi. Confronto di logaritmi, polinomi, esponenziali, fattoriale, n<sup>n</sup>. Svolgimento esercizio B1. Equazione di ricorrenza, maggiorazione, e primo esempio di applicazione del metodo di iterazione.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (D).</B> 

Dal libro di testo: esercizio 2.9, problema 2.2 e problema 2.4.

</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Lunedì 24 Marzo (2h)</b></font> - Esercizi.

<font color="#AF0F0F"><b>Giovedì 27 Marzo (3h)</b></font> - Caso migliore e caso peggiore, cenni al caso medio. Ricerca sequenziale. Ricerca binaria iterativa e ricorsiva, con analisi. Esercizi (parte del problema 2.2 nel libro, esercizio 1 appello del 3 luglio 2012).

<font color="#AF0F0F"><b>Lunedì 31 Marzo (2h)</b></font> - Ordinare in tempo _&Theta;(n<sup>2</sup>)_: insertionSort, selectionSort, bubbleSort. Proprietà invarianti per la dimostrazione di correttezza.

<font color="#AF0F0F"><b>Giovedì 3 Aprile (3h)</b></font> - Mergesort. Esercizi.

<font color="#AF0F0F"><b>Lunedì 7 Aprile (2h)</b></font> - Esercizi d'esame (soprattutto esercizi relativi alla progettazione di algoritmi): problema 2 dalla prova intermedia del 16 aprile 2013, problema 4 dalla prova intermedia del 26 aprile 2012 (testo 1), esercizio 1 dalla prova intermedia del 28 aprile 2011, esercizio 2 dalla prova intermedia del 29 aprile 2010. 

<font color="#AF0F0F"><b>Giovedì 10 Aprile (3h)</b></font> - Esercizi di preparazione alla prova intermedia: problema 2.10 del libro di testo, problema 5.2 del libro di testo, problema 3 della prova intermedia del 16 aprile 2013, esercizio 1 della prova intermedia del 23 aprile 2009, problema 3 della prova intermedia del 26 aprile 2012

<font color="#AF0F0F"><b>Lunedì 14 Aprile</b></font> - *Prova intermedia*

<font color="#AF0F0F"><b>Lunedì 28 Aprile (2h)</b></font> - Code con priorità: heap binari (definizioni, calcolo dell'altezza). Procedura fixheap, cancellazione del massimo, inserimento di una nuova chiave. Rappresentazione tramite vettore posizionale. Introduzione all'heapsort.

<font color="#AF0F0F"><b>Lunedì 5 Maggio (2h)</b></font> - Heapsort, ordinamento in loco. Costruzione ricorsiva di un heap in tempo lineare. Teorema master: enunciato, intuizione, esempi di applicazione. 

<font color="#AF0F0F"><b>Giovedì 8 Maggio (2h)</b></font> - Soluzione esercizi esonero.

<font color="#AF0F0F"><b>Lunedì 12 Maggio (2h)</b></font> - Lower bound al tempo di esecuzione di algoritmi di ordinamento basati su confronti. 

<font color="#AF0F0F"><b>Giovedì 15 Maggio (3h)</b></font> - Quicksort: partition in loco, partizioni bilanciate e sbilanciate, analisi nei casi peggiore e migliore, intuizione per l'analisi nel caso medio. Ordinare interi in tempo lineare: !CountingSort. Estensione a strutture arbitrarie: !BucketSort.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (E).</B> 

_Esercizi._ Svolgete gli esercizi 2.6, 2.7, 4.3, 4.4, 4.5, 4.12, 4.13, 4.14 dal libro di testo.

_Problemi._ Svolgete i problemi 4.1, 4.7, 4.8, 4.11 dal libro di testo.
</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Lunedì 19 Maggio (2h)</b></font> - Ordinamenti lineari: integerSort e bucketSort. Esercizi. Il problema della bandiera nazionale italiana.

<font color="#AF0F0F"><b>Giovedì 22 Maggio (3h)</b></font> - Rappresentazioni di alberi (di grado limitato o arbitrario): rappresentazioni indicizzate e collegate. Visita generica ed analisi (in funzione della rappresentazione dell'albero). Visita in ampiezza e visita in profondità iterativa e ricorsiva di alberi binari (preorder, inorder, postorder). Esercizio: ricostruire un albero binario dalle sue visite preorder e simmetrica (e varianti).

<font color="#AF0F0F"><b>Lunedì 26 Maggio (2h)</b></font> - Ancora sulle visite di alberi. Il tipo di dato astratto dizionario: effettuare ricerche in insiemi dinamici. Implementazioni banali: liste (ordinate e non) e array (ordinati e non). Alberi binari di ricerca (ABR): proprietà di ricerca, operzioni search e insert. Analisi dei tempi di esecuzione in funzione dell'altezza _h_ dell'albero. 

<font color="#AF0F0F"><b>Giovedì 29 Maggio (3h)</b></font> - ABR: calcolo del massimo in un sottoalbero e del predecessore di un nodo, operazione delete. Alberi AVL. Bilanciamento in altezza. Dimostrazione del fatto che l'altezza è logaritmica tramite alberi di Fibonacci. Operazione di inserimento. Rotazione di base e classificazione delle rotazioni: SS, DD, SD e DS.

<BLOCKQUOTE>
<B>Esercizi di riepilogo (F).</B> 

_Esercizi._ Svolgete gli esercizi 3.4, 3.5, 6.1, 6.2, 6.3, 6.10 (considerando solo ABR) dal libro di testo.

_Problemi._ Svolgete i problemi 3.3, 3.6, 3.8, 6.1 dal libro di testo.

Prova d'esame del _23 gennaio 2014_: esercizi 3 e 4

Prova d'esame del _4 giugno 2013_: esercizi 3, 4 e 5

Prova d'esame del _7 febbraio 2013_: esercizio 3

Prova d'esame del _17 gennaio 2013_: esercizi 3 e 4

Prova d'esame del _12 giugno 2012_: esercizi 4, 5 e 6

</BLOCKQUOTE> 

<font color="#AF0F0F"><b>Giovedì 5 Giugno (3h)</b></font> - Alberi AVL. Esercizi di preparazione all'esame.

<font color="#AF0F0F"><b>Lunedì 9 Giugno (2h)</b></font> - Esercizi di preparazione all'esame.

-->