Esercizio [grado] Dimostrare che in un grafo non diretto e connesso G ci sono sempre almeno due nodi che hanno lo stesso grado.
Esercizio [alberi] Dato un grafo diretto G, si spieghi come un suo nodo u con almeno un arco entrante ed almeno un arco uscente, possa finire nella foresta DFS prodotta da una visita in profondità di G, in un albero DFS che contiene solo u.
Esercizio [Hamiltoniano] Un cammino Hamiltoniano è un cammino (orientato) che passa per ogni nodo esattamente una volta. Descrivere un algoritmo che dato un grafo diretto e aciclico G, determina se G contiene un cammino Hamiltoniano. La complessità dell’algoritmo deve essere O(n + m).
Esercizio [lontani] Descrivere un algoritmo che, dato un grafo diretto G e un suo nodo s, restituisce il numero dei nodi raggiungibili da s che si trovano alla massima distanza da s. L'algoritmo deve avere complessità O(n+m).
Esercizio [copertura] Dato un grafo non diretto G si vuole trovare un suo albero di copertura. Si propone il seguente algoritmo:
INPUT un grafo non diretto G = (V, E)
SOL <- ∅
R <- {s} dove s è un qualsiasi nodo di V
WHILE E ≠ ∅ DO
Estrai un qualsiasi arco {u, v} da E
IF |{u, v} ∩ R| = 1 THEN
SOL <- SOL ∪ {{u, v}}
R <- R ∪ {u, v}
OUTPUT SOL
Esercizio [MaxST] Si consideri l'algoritmo di Prim modificato in modo che venga scelto ogni volta l’arco di peso massimo anziché quello di peso minimo. Provare che l'algoritmo trova l'albero di copertura di peso massimo o fornire un controesempio.
Esercizio [accoppiamento] Un accoppiamento in un grafo non diretto G è un sottoinsieme di archi disgiunti di G. Dato G si vuole trovare un accoppiamento di massima cardinalità. Viene proposto il seguente algoritmo greedy
INPUT un grafo non diretto G = (V, E)
SOL ← ∅
WHILE E ≠ ∅ DO
Tra gli archi in E prendi un arco {x, y} per cui il nodo x ha grado minimo
SOL <- SOL ∪ {{x, y}}
Cancella da E tutti gli archi che hanno per estremo x o y
OUTPUT SOL
Esercizio [conta] Dato un grafo diretto e pesato G ed un suo nodo s, l'algoritmo di Dijkstra calcola l'albero dei cammini minimi da s ad un qualsiasi altro nodo di G raggiungibile da s. In generale, tra il nodo s e un altro nodo u di G può esserci più di un cammino minimo. Dare lo pseudo-codice di un algoritmo che dato un grafo diretto G ed un suo nodo s, calcoli per ogni nodo u il numero di cammini distinti di peso minimo da s a u. Suggerimento: modificare l'algoritmo di Dijkstra. Discutere la complessità dell’algoritmo.
Esercizio [CD] Si supponga di voler creare un CD di brani musicali contente il maggior numero di brani dalla nostra collezione di musica. Si assuma che la somma delle dimensioni dei brani nella collezione ecceda la capacità del CD. Il problema sta nel selezionare un sottoinsieme degli n brani musicali che abbia cardinalità massima e che possa essere memorizzato sul CD.
Esercizio [continuo] Sia V un vettore di n interi. Si dice che V è continuo se per ogni indice i, 1 ≤ i ≤ n − 1, vale |V[i + 1] − V[i]| ≤ 1. Si dice zero del vettore un indice k tale che V[k] = 0.
Esercizio [somma] Sia A un vettore di n interi e x un intero. Descrivere un algoritmo che trovi, se esiste, una coppia di indici i, j tali che A[i] + A[j] = x. L'algoritmo deve avere complessità O(nlogn).
Esercizio [sottosequenza] Dare lo pseudo-codice di un algoritmo che data una sequenza di interi S trova una sottosequenza crescente di S di somma massima. Discutere la correttezza dell'algoritmo. L'algoritmo deve avere complessità O(n2).
Esercizio [prodotto] Dato un vettore V di n numeri razionali si vuole trovare un sottovettore il cui prodotto degli elementi sia massimo. Descrivere un algoritmo che risolve il problema in tempo O(n) e discuterne la correttezza.
Esercizio [sistemazioni] Si supponga di avere n elementi identificati dagli interi 1,…,n, da sistemare in p posizioni {1,2,…,p} con n ≤ p. Una sistemazione S è lecita se vale S[i] < S[i + 1] dove S[i] è la posizione assegnata all’elemento i. Si dispone di una matrice n×p di interi non necessariamente positivi dove M[i, j] rappresenta il valore che si ottiene assegnando la posizione j all'elemento i. Il valore di una sistemazione è dato dalla somma dei valori ottenuti dagli n posizionamenti scelti.
Esercizio [esami] Sia dato un insieme di n esami identificati dagli interi 1,2,…,n. Ogni esame i vale ci crediti ed ha un grado di difficoltà di. Ogni studente può redigere il proprio piano di studio individuale scegliendo nella lista degli esami attivati un sottoinsieme di esami tali che la somma dei crediti corrispondenti sia almeno C. Descrivere un algoritmo che redige un piano di studi regolare di difficoltà (la somma dei gradi di difficoltà degli esami del piano) minima in tempo O(nC). Discutere la correttezza dell'algoritmo.
Esercizio [pari] Dare lo pseudo-codice di un algoritmo che, preso in input un intero n, stampi tutti i sottoinsiemi di {1,2,…,n} che contengono almeno un elemento che è un numero pari. La complessità dell’algoritmo deve essere O(nS(n)), dove S(n) è il numero di sottoinsiemi da stampare.
Esercizio [abc] Dare lo pseudo-codice di un algoritmo che, preso in input un intero n, stampi tutte le stringhe di lunghezza n sull'alfabeto {a, b, c} tali che il numero di occorrenze di a è minore o uguale al numero di occorrenze di b che a sua volta è minore o uguale al numero di occorrenze di c. Ad esempio se n = 3 allora l'algoritmo deve produrre (non necessariamente in quest'ordine): ccc, bcc, cbc, ccb, abc, bac, bca, acb, cab e cba. La complessità dell'algoritmo deve essere O(nS(n)), dove S(n) è il numero di stringhe da stampare.
Esercizio [matrici] Dare lo pseudo-codice di un algoritmo che, preso in input un intero n, stampi tutte le matrici n×n con valori in {a, b, c} tali che due elementi adiacenti (per riga o colonna) abbiano valori differenti. Ad esempio se n = 2, le matrici da stampare sono:
ab ab ab ac ac ac ba ba ba bc bc bc ca ca ca cb cb cb
ba bc ca ca cb ba ab ac cb cb ca ab ac ab bc bc ba ac
La complessità dell'algoritmo deve essere O(n2S(n)), dove S(n) è il numero di matrici da stampare.