• Non ci sono risultati.

008AA – ALGORITMICA E LABORATORIO

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "008AA – ALGORITMICA E LABORATORIO"

Copied!
1
0
0

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

Scarica adesso ( 1 pagine )

Testo completo

(1)

008AA – ALGORITMICA E LABORATORIO 14 Gennaio 2015

Cognome Nome: N. Matricola: Corso: A B

Esercizio 1. (10 punti) Si consideri un array a non ordinato di n chiavi intere, di valore compreso nell’in- tervallo [0, k], con k = O(n). Si dia il codice di un algoritmo che con un’unica scansione di a conti il numero r di chiavi con almeno un duplicato in a. Si analizzi la complessit`a in funzione di n e di k.

Esercizio 2. (10 punti)

Dato un array a di n interi, progettare un algoritmo efficiente che costruisca ricorsivamente un albero binario bilanciato tale che a[i] sia l(i+1)-esimo campo u.dato in ordine di visita posticipata. Si analizzi la complessit`a dell’algoritmo proposto, indicando e risolvendo la corrispondente relazione di ricorrenza.

Esercizio 3. (10 punti)

Progettare un algoritmo efficiente che restituisca il numero minimo di archi da aggiungere ad un grafo non orientato per renderlo connesso.

Esercizio 4. (3 punti)

Rappresentare l’albero in figura in notazione binarizzata.

Memorizzazione binarizzata

•  Campi u.dato, u.padre, u.fratello (fratello successivo) e u.primo (primo figlio)

•  Accesso al figlio i --> O(i+1) tempo

Riferimenti

Scarica adesso ( PDF - 1 pagine - 134.72 KB )

Documenti correlati

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

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

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

008AA – ALGORITMICA E LABORATORIO

Progettare e descrivere in pseudocodice un algoritmo di tipo divide et impera per calcolare la somma di n interi positivi, ciascuno di valore Θ(1), memorizzati in un array1.