*** Lezione 1, 28 Febbraio 2013 ***

1. Definire e inizializzare in Java un array di N numeri interi *distinti* (la 
   scelta di N e degli elementi dell'array è arbitraria). Definire una funzione 
   search che, presi in input un array A e un numero intero x, restituisca:
     i, se l'(i+1)-esimo elemento di A è x (cioè, A[i] == x);
    -1, se l'elemento x non occorre in A (cioè, per ogni 0 <= i < N, A[i] != x).
   Testare la funzione search con un piccolo programma di prova.
   Es. N = 5, A = [3, 0, 4, -2, 9] --> search(A, -2) = 3, search(A, 1) = -1 
   
2. Ripetere l'esercizio 1, utilizzando però numeri interi distinti e *ordinati* 
   in ordine crescente: A[0] < A[1] < ... < A[N - 2] < A[N - 1].
   Considerando tale pre-condizione, la funzione search può essere migliorata?

*** Lezione 2, 07 Marzo 2013 ***

1. Provare a risolvere gli esercizi 2.1, ..., 2.11 del libro di testo.

2. Seguendo gli esempi visti a lezione, implementare in Java gli algoritmi 
   mergeSort e countingSort.

*** Lezione 3, 13 Marzo 2013 ***

1. Riguardare e provare a correggere l'esercizio 2.1; la soluzione corretta è 
   19, log^2(n), n^(1/2), n/log(n), n^4 - 7n^3, n^5 - 5n^2, n^(log(n)), 3^(n-2),
   pi^n, log^n(n).

2. Provare a risolvere gli esercizi 2.12, ..., 2.16 del libro di testo.

3. Implementare e testare in Java gli esercizi 2.9, 2.10 e 2.11

*** Lezione 4, 21 Marzo 2013 ***

1. Provare a risolvere l'esercizio 2.16 utilizzando il Master Theorem:
   http://it.wikipedia.org/wiki/Teorema_principale_(informatica)
   
2. Implementare in Java le strutture dati Lista, Pila e Coda.

*** Lezione 5, 04 Aprile 2013 ***

1. Provare ad implementare in Java altre strutture dati (come ad es. grafi, 
   insiemi, dizionari ma anche strutture "numeriche" come ad es. numeri 
   razionali o complessi).

*** Lezione 6, 11 Aprile 2013 ***

1. Implementare in Java il Pigeonhole Sort. Risolvere l'esercizio 7.2 come 
   nella versione originale del libro (m = 11). Il vettore risultante è
   [33, 23, 24, 14, 11, 16, 13, 18, x, 31, 10], la cella x rimane vuota in 
   quanto il valore 18 non può essere inserito; il numero medio di accessi 
   è 1.2 per i valori che è stato possibile inserire.

*** Lezione 7, 18 Aprile 2013 ***

1. Dimostrare che se un grafo G(V,E) non contiene circuiti di lunghezza dispari 
   è bipartito (sugg: agire costruttivamente, partendo da un nodo arbitrario e 
   considerare iterativamente i nodi adiacenti)

2. Scrivere lo pseudocodice (ed eventualmente l'implementazione Java) per il 
   calcolo del diametro di un grafo.

*** Lezione 8, 24 Aprile 2013 ***

1. Trovare un caso in cui Dijkstra funziona bene anche con pesi negativi.

2. Fornire una versione iterativa dell'esercizio 12.11

3. Dimostrare che un MST contiene sempre i due archi e1 ed e2 con peso minimo.

*** Lezione 9, 2 Maggio 2013 ***

1. Generalizzare il caso particolare n = 2 visto a lezione per l'algoritmo di 
   riempimento della matrice attraverso il flusso massimo (es. 15.4)

2. Implementare l'algoritmo che riempe la matrice in O(n^2)

3. Implementare in Java gli esercizi 16.4 e 16.6