=== Testo di esame Fondamenti di Informatica 15 giugno 2015 ===

			--- Domanda A ---

Sia dato un vettore v che contiene elementi della forma
      { descrizione: <stringa>, prezzo: <intero>, quantita: intero }
Si scriva una funzione pmin(v) che riceve in ingresso v e
restituisce il prezzo minimo tra tutti gli elementi del vettore.

--- Soluzione:

Il problema si risolve semplicemente scandendo il vettore e
tenendo traccia del prezzo minimo incontrato durante la scansione.
La complessita` della funzione e` O(N) con N numero di elementi del
vettore

	function pmin(v) {
	    var i, x; /* valore minimo incontrato finora */
	    if (v == null || v.length == 0) {
		/* vettore non esistente o vuoto */
		return 0;
	    }
	    x = v[0].prezzo; /* punto di partenza */
	    for (i = 1; i < v.length; i++) {
		if (v[i].prezzo > x) {
		    x = v[i].prezzo;
		}
	    }
	    return x;
	}

		    ---- Domanda B ----

Sia dato un vettore v che contiene dati della forma
      { colore: <stringa>, prezzo: <intero>, ... }
Si vuole realizzare una funzione allcolors(v) che riceve in ingresso v e
restituisce una lista che contiene l'elenco dei colori degli
elementi presenti nel vettore.
Descrivere a) l'algoritmo seguito, b) la sua complessita` e infine
scrivere la funzione.

---- Soluzione:

In questo caso la soluzione piu` semplice sfrutta una mappa per
tener traccia dei colori visti finora ed evitare di ripetere
un colore piu` volte.

	function allcolors(v) {
	    var i, l = null /* lista */, m = {} /* mappa di appoggio */ ;
	    var col; /* colore corrente */
	    if (v == null || v.length == 0) {
		/* vettore non esistente o vuoto */
		return 0;
	    }
	    for (i = 0; i < v.length; i++) {
		col = v[i].colore;
	 	if (m[col] === undefined) { /* nuovo colore */
		    /* crea nuovo elemento e lo aggiunge in testa */
		    l = { colore: col; next: l};
		    m[col] = 1; /* ricorda che abbiamo gia` visto il colore */
		}
	    }
	    return l;
	}

			---- Domanda C ----
Sia data una lista unidirezionale l che contiene elementi della forma
{ nome: <stringa>, anno: <intero>, next: <riferimento>, ... }
Si vuole realizzare una funzione bidir(l) che trasforma la lista
in una lista bidirezionale, aggiungendo ad ogni elemento il riferimento
all'elemento precedente.
Descrivere a) l'algoritmo seguito, b) la sua complessita' e infine
scrivere la funzione.

--- Soluzione:

Per questo problema bisogna scandire la lista aggiungendo ad ogni
elemento un campo che punta all'elemento precedente.
La complessita` e` O(N).

	function bidir(l) {
	    var cur = l;

	    if (l == null) { return; } /* lista vuota */
	    l.prev = null; /* il primo elemento non ha precedente */
	    while (cur.next != null) {
		cur.next.prev = cur;
		cur = cur.next;
	    }
	    return;
	}