ALGORITMI I
Prof.ssa Petreschi   Prof. Silvestri   Dott.ssa Calamoneri
16/1/2006

ESERCIZIO 1
Valutare la complessità asintotica, nel caso peggiore, del seguente programma Cnt che, presi in input due vettori A, B e le loro dimensioni, rispettivamente n ed m, conta il numero di elementi in comune tra i due vettori. Effettuare la valutazione in funzione delle dimensioni dei due vettori e mostrare il procedimento usato.

int Cnt(int A[], int n, int B[], int m)
{
    if (n >= 2) {
        return Cnt(A, n/2, B, m) + Cnt(A + n/2, n - n/2, B, m);
    } else {
        int k, c = 0;
        for (k = 0 ; k < m ; k++) 
            if (B[k] == A[0]) c++;
        return c;
    }
}

ESERCIZIO 2
Scrivere in C una funzione che, preso in input un grafo G non diretto, rappresentato tramite matrice di adiacenza, restituisca il complemento di G (cioè, il grafo che ha l'insieme degli archi uguale al complemento dell'insieme degli archi di G) rappresentato tramite liste di adiacenza. Valutare la complessità del programma.

ESERCIZIO 3
Dato il grafo non diretto G, tramite matrice di incidenza qui sotto riportata, a partire dal vertice a generare tutti gli alberi ottenibili con visite in ampiezza e in profondità. Per ogni albero, riportare la sequenza dei vertici nell'ordine in cui sono visitati.
    a  1 1 0 0 0 0 0
    b  1 0 1 1 0 0 0
    c  0 1 1 0 1 0 1
    d  0 0 0 1 1 1 0
    e  0 0 0 0 0 1 1