Laboratorio di Informatica 2 (Algoritmi)
A.A. 2002-2003

ESERCITAZIONI

Ogni esercitazione può essere svolta da uno o due studenti. Questa consiste nel produrre  un codice  in C secondo la traccia data e di realizzare delle prove di esecuzione significative ai fini del progetto.
Dovranno poi essere consegnati due file: uno contenente il codice C e l'altro  in cui si descrivono brevemente le prove di esecuzioni del programma effettuate e si espongono brevemente osservazioni/commenti/conclusioni relative a queste.

Entrambi i file dovranno contenere al loro interno il nome/i nomi degli autori. Il nome dei file dovrà essere quello dell'autore seguito dal numero dell'esercitazione. Tali file dovranno essere spediti come allegati di un messaggio di e-mail indirizzato a:   labinfo2@mat.uniroma2.it
Chi dovesse avere problemi con l' e-mail può consegnare  un dischetto.

I criteri di valutazione delle esercitazioni comprendono: chiarezza, eleganza ed efficienza del codice C. Numero e significatività delle prove di esecuzione. Chiara esposizione di osservazioni e conclusioni sulla implementazione e sui risultati ottenuti  dall'esecuzione  su input diversi per dimensioni e proprietà. Puntualità delle consegne.

• ESERCITAZIONE 1  (da consegnare preferibilmente entro il 6 maggio)
  Implementare un programma per testare uno a scelta tra i due semplici algoritmi selection sort e bubble sort su input di diverse tipologie (array ordinato, array ordinato   al contrario, array casuali). L'output di tale programma dovrà essere  il numero di confronti/scambi effettuati dall'algoritmo nei vari array dati in input (ad esempio in forma di tabella o di grafico). Eseguire il programma su array di varie lunghezze e cercare di calcolare empiricamente le funzioni complessità relativamente al numero di confronti e/o al numero di scambi effettuati dall'algoritmo.
  
• ESERCITAZIONE 2  (da consegnare entro il 13 maggio)
  Implementare un programma per confrontare (relativamente al numero di confronti e/o scambi effettuati) i tre algoritmi di ordinamento selection sort, bubble sort e insertion sort. Calcolare la media (dei confronti e/o scambi) su almeno 20 vettori random. Calcolare inoltre i confronti e/o scambi sul vettore completamente ordinato, sul vettore ordinato al contrario e sul vettore con tutti i valori uguali tra loro tranne uno.  L'output di tale programma dovrà essere  il numero di confronti/scambi effettuati dai tre algoritmi nei tre tipi di array descritti e i valori della media  dei 20 (o piu') vettori casuali. L'output potrà essere, ad esempio, in forma di tabella. L'output dovra' essere relativo a due diverse dimensioni di vettore che siano una "piccola" e una "grande"  (esempio: 10 e 100 oppure 50 e 1000,.....).

• ESERCITAZIONE 3  (da consegnare entro il 20 maggio)
  Implementare un programma per testare il numero di  confronti effettuati da  merge sort, su diverse tipologie di input (vettore completamente ordinato, sul vettore ordinato al contrario e sul vettore con tutti i valori uguali tra loro tranne uno) e per due diverse dimensioni del vettore: una "piccola" e una "grande". (Vedi Esercitazione 2).
  Confrontare (sempre relativamente ai confronti effettuati)  merge sort ed  insertion sort su input random di taglia N "piccola". Partire, ad esempio, da N=5, e poi incrementare di 5 (5,10, 15, 20, 25,...) arrivando, ad esempio, a 100. Dall'output, si dovrebbe poter valutare da quale valore soglia di N  merge sort va meglio di  insertion sort.  Confrontare poi i due algoritmi su valori di input grandi. Partire, ad esempio, da N=100, e poi incrementare di100  (100,200, 300,...) arrivando, ad esempio, a 1000 (o a 10000). Commentare i risultati ottenuti.
  
  Facoltativo : Implementare un algoritmo "misto" che usa merge sort per dimensione di input maggiore di un certo S mentre usa   insertion sort per dimensioni sotto il valore soglia S. Confrontare tale algoritmo misto sia con insertion sort che con merge sort per le varie dimensioni di input sopra descritte.Fare eventualmente varie prove con diversi valori di S. Commentare i risultati ottenuti.

• ESERCITAZIONE 4  (da consegnare entro il 27 maggio)
  Implementare un programma per testare il numero di  confronti e di scambi effettuati da  heap sort, su diverse tipologie di input (vettore completamente ordinato, sul vettore ordinato al contrario e sul vettore con tutti i valori uguali tra loro tranne uno) e per due diverse dimensioni del vettore: una "piccola" e una "grande". (Vedi Esercitazione 2).
  Realizzare le tre tabelle di confronto seguenti:
  1. Numero di confronti effettuati da  merge sort ed  heapsort sort e, facoltativamente, anche dal "merge-insertion" (vedi Esercit. 3)
  2. Numero di confronti effettuati da  insertion sort ed  heapsort sort
  3. Numero di confronti e di scambi effettuati da  bubble sort ed  heapsort sort
  Le tre tabelle dovrebbero essere riferite a vari input random di taglia N "piccola". Partire, ad esempio, da N=5, e poi incrementare di 5 (5,10, 15, 20, 25,...) arrivando, ad esempio, a 100. E poi a vari input grandi. Partire, ad esempio, da N=1000, e poi incrementare di 500  (1000,1500, 2000,...) arrivando, ad esempio, a 10000. (Duqnue le tabelle sono 6 in tutto).Commentare i risultati ottenuti.
  Nota: il confronto va fatto ordinando lo stesso vettore!