Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Study material for Algoritmi e Principi dell'Informatica, shared by the Studwiz community and reviewed by moderators.
Import quality: text was extracted directly from the original document.
Representative passages recognised in different parts of the material. The full extracted text remains available to search, while this compact preview makes the page easier to read.
Algoritmi e Principi dell'Informatica Seconda Prova in Itinere 13 Febbraio 2015 Avvisi importanti Il tempo a disposizione è di 1 ora e 45 minuti. Esercizio 1 (punti 5/15-esimi) Si calcoli la complessità del seguente frammento di codice ossatura di una funzione f applicata a un array A: f(A): n := A.length i := 1 altre eventuali inizializzazioni eseguite in tempo costante while i < n do_something_in_tempo_costante i := i*2 f(A[1..n/3]) f(A[n/3+1..(2/3)*n]) j := 2 while j < n*n do_something_in_tempo_costante j := j*j return result Esercizio 2 (punti 7/15-esimi) Si consideri un albero rosso-nero di altezza nera bh e costituito da soli nodi neri. 1. Quali sono, rispettivamente, il numero minimo e massimo di nodi contenuti lbero? (si precisi se nel conto viene incluso il nodo T.NIL o no). 2. -nero costituito da soli nodi neri applicandovi esclusivamente operazioni di inserimento di nuovi nodi? In caso positivo in che modo? (eventualmente illustrandolo mediante un semplice esempio). 3. Qual è il numero massimo di nuovi nodi che si possono inserire in esso senza effettuare cancellazioni e senza alterare bh? Si forniscano brevi ma chiare spiegazioni per le risposte date. Esercizio 3 (punti 7/15-esimi) Sia dato un grafo G e due sottoinsiemi dei suoi vertici, V1 e V2. La distanza tra V1 e V2, d(V1, V2), è la distanza minima tra un nodo appartenente a V1 e un nodo appartenente a V2. Se V1 e V2 non sono disgiunti allora la loro distanza è uguale 0. Si specifichi un algoritmo che, a partire da un grafo G e da due suoi sottoinsiemi V1 e V2, calcoli la distanza tra V1 e V2; se ne discuta quindi la complessità . La valutazione dell dipenderà ovviamente dalla sua complessità. N.B.: Si può assumere che esista una funzione che in tempo costante vertice a uno dei due insiemi. Tracce di…
First page of the document.
