008AA – ALGORITMICA E LABORATORIO

Calcolare la visita DFS su G e si mostri l’albero DFS specificando anche il tipo di archi individuati dalla visita (ossia dell’albero, indietro, in avanti, attraversamento – o

(4+3+3 punti) Si progetti un algoritmo ricorsivo basato sulla tecnica Divide et Impera che calcola il secondo elemento pi` u grande di un vettore A di n interi, senza modificarlo..

(4+4) Si definisca la relazione che consente di calcolare mediante Programmazione Dinamica la Edit Distance di due stringhe S1 e S2, nell’ipotesi che l’errore di mismatch abbia costo

• Si diano le regole per navigare sull’heap ternario, cio` e le regole per cui, dato il nodo i, si possa accedere direttamente ai 3 figli o al padre.. • Si fornisca l’algoritmo

Dato un albero binario T in cui ogni nodo contiene un intero positivo, diciamo che la media di un sottoalbero non vuoto ` e la somma degli interi contenuti nei suoi nodi diviso

Dato un albero binario T di n nodi, scrivere lo pseudocodice di un algoritmo efficiente che restituisce TRUE se per ogni nodo u di T vale la seguente propriet` a: il

In caso di risposta affermativa al punto 2, disegnare l’albero di decisione corrispondente all’algoritmo trovato che risolve il problema con due

Un grafo non orientato ` e detto 2-colorabile se ` e possibile attribuire a ogni vertice uno tra due colori in modo che vertici adiacenti siano colorati con colori distinti..