• Non ci sono risultati.

008AA – ALGORITMICA E LABORATORIO

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "008AA – ALGORITMICA E LABORATORIO"

Copied!
2
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 2 pagine )

Testo completo

(1)

008AA – ALGORITMICA E LABORATORIO Appello dell’11 febbraio 2020: Soluzioni

Esercizio 1: soluzione.

1. T (n) = T (n/4) + O(√ n).

2. La soluzione della ricorrenza `e T (n) = O(√

n) (Teorema fondamentale, terzo caso).

Esercizio 2: soluzione

(2)

Esercizio 3: soluzione.

• Si visita il grafo con una BFS per calcolare le distanze dei vertici dalla sorgente

• Si calcola e si restituisce la media delle distanze

• Il costo `e pari a Θ(|V | + |E|) (il grafo `e connesso e la visita raggiunge tutti i vertici)

Esercizio 4: soluzione.

1. Il limite inferiore `e Ω(n) in quanto `e necessario leggere tutti i dati di ingresso.

2. Il costo al caso medio `e Θ(n) e si ottiene valutando il numero di confronti in tutti i casi che si possono verificare:

– chiave presente in posizione 1: 1 confronto – chiave presente in posizione 2: 2 confronti

...

– chiave presente in posizione n: n confronti

Nell’ipotesi in cui gli n casi siano equiprobabili, si ottiene:

Tmedio(n) = 1

n · (1 + 2 + . . . + n) = 1

n · n(n + 1)

2 = n + 1

2 = Θ(n) .

Riferimenti

Scarica adesso ( PDF - 2 pagine - 488.67 KB )

Documenti correlati

008AA – ALGORITMICA E LABORATORIO

(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..

008AA – ALGORITMICA E LABORATORIO

(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

008AA – ALGORITMICA E LABORATORIO

• 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

008AA – ALGORITMICA E LABORATORIO

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

008AA – ALGORITMICA E LABORATORIO

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

008AA – ALGORITMICA E LABORATORIO

Lo pseudocodice della procedura split , richiamata su un nodo con ⇣ figli, `e inoltre mostrato in Figu- ra 6.23 (lo pseudocodice non mostra come aggiornare i campi ed ⇥ di ciascun

008AA – ALGORITMICA E LABORATORIO

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

008AA – ALGORITMICA E LABORATORIO

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..