====== Soluzioni del compito del 9/7/2008 ======
Soluzione per gli esercizi 2, 3 e 5

===Esercizio 2===
Il testo chiede di determinare l'output del seguente programma Python:
<code python>
def f(x,y):
        return x+y*2

def g(x,y=[1]):
        return x>y

a=[1,2]
b=['a','b']

print g(f(a,b))
print f(b,a)
print g(f(a,b),f(b,a))

def h(y):
        def f(x):
                return x+y
        return f

f=h(a)
print f(b)
</code>

La risposta corretta e':
   True
   ['a', 'b', 1, 2, 1, 2]
   False
   ['a', 'b', 1, 2]
Bisogna infatti ricordare che l'operazione di confronto si applica fra liste di qualunque lunghezza, e l'operatore * applicato ad una lista ed un numero intero //n// restituisce una nuova lista pari alla lista originale replicata //n// volte.
Per seconda parte, la funzione //f=h(x)// esegue la somma (o la concatenazione, nel caso delle liste) fra //x// e l'argomento di //f//. 

===Esercizio 3===
Gli ultimi due casi si risolvono applicando il teorema maestro.
Il primo si svolge considerando che T(n) = T(n-3) + lg n = lg n + lg n-3 + lg n-6 ... = Θ(n lg n).

===Esercizio 5===
Se l'albero, per essere valido, deve avere in ogni nodo un'etichetta pari alla somma delle etichette nei sottoalberi, allora e' anche vero che in ogni nodo l'etichetta deve essere pari al //doppio// della somma delle etichette dei figli (a meno che i figli non siano foglie). Di conseguenza, si puo' scrivere una soluzione (in Python) in questo modo:

<code python>
def check(node):
        if node.isLeaf() :
                return True
        sum = 0
        for c in node.children :
                if c.isLeaf() :
                        sum+=c.value
                else :
                        sum+=c.value*2
        if sum != node.value :
                return False
        return reduce(lambda x, y: x and y, [ check(c) for c in node.children ], 1)
</code>

La complessita' di questa soluzione e' O(n) nel numero dei nodi.