Esame - #3 - 7 Giu 2023

[notedo]

Soluzione Prof

[ZGianluigi]

🟡 Codice giusto, costo computazionale sbagliato (vedere sotto per soluzione completa) @rimaout

a) Pseudocodice con test

class Nodo:
    def __init__(self, key, left=None, right=None):
        self.key = key
        self.left = left
        self.right = right

def contaNodi(r):
    # Funzione ricorsiva che calcola il numero di nodi con esattamente 2 figli e chiave pari
    if r is None:
        return 0

    # Controlla se il nodo corrente ha esattamente 2 figli e una chiave pari
    count = 0
    if r.left is not None and r.right is not None and r.key % 2 == 0:
        count = 1

    # Somma il risultato della chiamata ricorsiva sul sottoalbero sinistro e destro
    count += contaNodi(r.left)
    count += contaNodi(r.right)

    return count

# Esempio di utilizzo:
#         4
#        / \
#       2   6
#          / \
#         5   7
r = Nodo(4, Nodo(2), Nodo(6, Nodo(5), Nodo(7)))
print(contaNodi(r)) # Output: 2

# Un altro esempio
#         8
#        / \
#       3   4
#      /   / \
#     2   6   10
#          \
#           7
r = Nodo(8, Nodo(3, Nodo(2)), Nodo(4, Nodo(6, None, Nodo(7)), Nodo(10)))
print(contaNodi(r))  # Output: 2 (nodi con chiave 8 e 4)

b) Costo computazionale

L'algoritmo ha un costo computazionale di O(n) dove n è il numero di nodi dell'albero. Questo perché i nodi vengono visitati solo una volta.

[alem1105]

🟢 Tutto giusto

| Pseudocodice Python

def esame(T):
    if T == None:
        return 0
    if T.left == T.right == None:
        return 0
    to_ret = 0
    if T.key % 2 == 0 and T.left != None and T.right != None:
        to_ret = 1
    return esame(T.left) + esame(T.right) + to_ret

| Costo Computazionale

Utilizziamo il metodo di sostituzione per dimostrare che $T(n) = \theta(n)$.

| Equazione di ricorrenza:

Indichiamo con $k$ il numero di nodi del sottoalbero sinistro.

$T(n) = T(k) + T(n - k - 1) + \theta(1) $ $T(1) = \theta(1)$

Senza asintotica per le dimostrazioni:

$T(n) = T(k) + T(n - k - 1) + b $ $T(1) = a$

1) Dimostrazione $T(n) = O(n)$

• Caso Base $T(1) \leq cn$ $a\leq c$

• Passo Induttivo Ipotesi: $T(k) \leq ck$ $T(n - 1 - k) \leq c(n - 1 -k)$

  $T(n) \leq cn$ - Sostituisco $T(n)$ $T(k) + T(n - 1 - k) + b \leq cn$ $ck + cn - c - ck + b \leq cn$ -> $c \geq b$

  $T(n) = O(n)$ per una costante $c\geq max(a,b)$

2) Dimostrazione $T(n) = \Omega(n)$

• Caso Base $T(1) \geq cn$ $a\geq c$

• Passo Induttivo Ipotesi: $T(k) \geq ck$ $T(n - 1 - k) \geq c(n - 1 -k)$

  $T(n) \geq cn$ - Sostituisco $T(n)$ $T(k) + T(n - 1 - k) + b \geq cn$ $ck + cn - c - ck + b \geq cn$ -> $c \leq b$

  $T(n) = \Omega(n)$ per una costante $c\leq min(a,b)$

3) Dato che $T(n) = O(n)$ e $T(n) = \Omega(n)$ allora $T(n) = \theta(n)$

[rimaout]