(sono quelli specificati a lezione e presenti sui lucidi)

Scrivere una funzione

int* random_array(int n)

che restituisce un array contenente n elementi casuali (va allocato sullo heap!! altrimenti viene deallocato!)

Utilizzare la funzione per scrivere due programmi C distinti che creano un array e lo ordinano con selection sort, oppure quicksort.

Osservare le differenze di performance tra i due algoritmi al crescere di n (e.g., n > 1000000) misurando il tempo necessario all'ordinamento

Dato un array di interi ordinato, come posso verificare se contiene un intero x? Devo davvero leggere ogni valore, o esiste un modo più veloce?

Scrivere un programma che legga da tastiera una sequenza di n interi NON distinti e li inserisca (senza duplicati) in una tabella hash di dimensione $m=2n$ utilizzando liste di trabocco per risolvere conflitti. Utilizzare la funzione hash $h(x) = ((ax + b) \% p)\%m$ dove $p$ è il numero primo $999149$ e $a$ e $b$ sono interi positivi minori di 10.000 scelti casualmente.

Una volta inseriti tutti gli interi, stampare

1. gli elementi nella tabella
2. il numero totale di conflitti,
3. la lunghezza massima delle liste e
4. il numero di elementi distinti nella tabella.

Provare lo stesso con funzione hash $h(x) = x\%m$ e osservare se c’è differenza nella performance.