Primo appello sessione estiva

E' stata attivata la prenotazione per lo scritto di giugno sul Totem.

Si ricorda che la prenotazione allo scritto e' obbligatoria.

Fine lezioni

Oggi si e' svolta l'ultima lezione del corso. Grazie per l'attenzione ed in bocca al lupo per l'esame.

Lezione del 31/5/2010

Ancora sul ri-bilanciamento di alberi AVL a seguito dell'inserimento di un nodo. Esercizi: come ricalcolare le altezze dei sottoalberi di un ABR a seguito dell'inserimento di un nuovo nodo.

Lezione del 26/5/2010

Alberi binari di ricerca (ABR): codice della funzione di inserimento; cancellazione di un nodo. Mantenere il bilanciamento degli ABL con gli alberi AVL: ribilanciamento di un albero AVL dopo una operazione di modifica dell'albero.

Lezione del 24/5/2010

Alberi binari di ricerca (ABR): funzioni di ricerca generica, ricerca minimo ed inserimento; rappresentazione in C degli ABR; codice per ricerca generica e ricerca minimo.

Lezione del 17/5/2010

Ricerca binaria su un vettore ordinato: algoritmo di complessita' logaritmica nel numero di elementi del vettore; limite inferiore sulla complessita', ovvero ottimalita' dell'algoritmo di ricerca binaria.

Avviso

In occasione della settimana di mobilitazione degli Atenei Italiani contro il DDL Gelmini, e' stata deliberata la sospensione della didattica nei giorni 18 e 19 maggio. Pertanto La lezione del 19/5 non si svolgera' e verra' recuperata a Giugno.

Avviso

Il ricevimento studenti di oggi (17/5) non si terra'.

Lezione del 12/5/2010

Esercizi: riparazione dello Heap dopo la modifica del peso di un suo nodo (codice della funzione al termine del post); confronto tra stringhe.

Codice della funzione heapModify proposto dallo studente Fabio Durastante.

/*La funzione prende in input l'Heap H, 
il numero del nodo da modificare 
e il suo nuovo peso. */
Heap heapModify(Heap H, int u, int e){
 if(u>H.n||u==0) return H;
 /* si porta il nodo verso la radice */
 if(H.v[u]>e){ 
  H.v[u]=e; 
  while( u>1 && H.v[u]<H.v[u/2]){ 
   swap(&(H.v[u]),&(H.v[u/2]));
   u=u/2;
  }
  return H;
 }
 if(H.v[u]<e){
  /* ... altrimenti si porta il nodo
  verso le fogli */
  H.v[u]=e; 
  while(2*u+1<=H.n &&(H.v[u]>H.v[2*u]||H.v[u]>H.v[2*u+1])){ 
   if(H.v[2*u]<H.v[2*u+1]){
    swap(&(H.v[u]),&(H.v[2*u]));
    u=2*u;
   } else{
    swap(&(H.v[u]),&(H.v[2*u+1]));
    u=2*u+1;
   }
  }
  if(2*u<H.n && H.v[u]>H.v[2*u])
   swap(&(H.v[u]),&(H.v[2*u]));
  return H;
 }
 /* ... non occorre nessuna modifica. */
 H.v[u]=e;
 return H;
}

Lezione del 3/5/2010

Esercizi: Rappresentazione della coda con liste circolari doppiamente linkate; Inversione di una lista.

Lezione del 10/5/2010

Rappresentazione degli Heap con vettore: implementazione in C delle funzioni di accesso e cancellazione del minimo, inserimento di un nuovo elemento. L'algoritmo di ordinamento ottimo Heap-Sort.

Lezione del 5/5/2010

Code con priorita' ed Heap: operazioni di inserimento e cancellazione del minimo dall'heap in tempo logaritmico nella dimensione della struttura.