Tarea 3
Fecha de entrega: miércoles 29 de septiembre de 2021

1. Recorrido de un árbol

 EL siguiente pseudocódigo es un algoritmo estándar para recorrer
un árbol para contar el número de nodos de un árbol R.
La llamada inicial es cuenta_nodos( raiz[R] ).

cuenta_nodos( x )
1 if n = NIL
2    return 0
3 else 
4    return 1 + cuenta_nodos( izquierda[x] )
5             + cuenta_nodos( derecha[x] )

Defina como tamaño(x) el número de nodos en el subárbol
con raíz en el nodo x \in R, y sea T(x) el tiempo de ejecución
en el peor caso de cuenta_nodos( x ).

 (a) De una recurrencia para T(x) en términos de izquierda(x) y derecha(x)
 (b) Use el método de sustitución para probar que T(x)=O( size(x) ).

Una optimización común del compilador en este pseudocódigo, llamada
"recursión de cola" , es reemplazar una de las llamadas recursivas
con un ciclo, resultando en el siguiente pseudocódigo:

cuenta_nodos_en_cola( x )
1 s = 0
2 while x != NIL
3    do
4        s = s + 1 ´+ cuenta_nodos_en_cola( izquierda[x] )
5        x = derecha[x]
6 return s

Sea derecha^i[x] para escribir el i-ésimo descendiente de x, esto es

               | x                            si i = 0 
derecha^i[x] = | 
               | derecha[ derecha^{i-1}[x] ]  si i > 0

Considere invariante de ciclo

   s = k + sum_{i=0}^{k-1} cuenta_nodos_en_cola( izquierda[ derecha^i[x] ] )   (1)

donde k>0 es el número de veces que el ciclo while (lineas 2-5)
en cuenta_nodos_en_cola ha sido ejecutado.

 (c) pruebe que si la ecuación (1) se mantiena para k, entonces esta se mantiene
    para k+1

2. Multiplicación polinomial

Si se tienen dos polinomios lineales ax + b  y  ´cx + d,
se pueden multiplicar usando las cuatro multiplicaciones
de coeficientes

m1 = a c,
m2 = a d
m3 = b c,
m4 = b d

para formar el polinomio

m1 x^2 + (m2 + m3) x + m4.

 (a) De un algoritmo divide y vecerás para multiplicar dos polinomios
    de grado n basado en esta fórmula
 (b) De una recurrencia para el tiempo de ejecución en el peor caso
   para el algoritmo
 (c) Muestre cómo muiltiplicat dos polinomios lineales ax+b y cx+d usando
   solo tres multiplicaciones de coeficientes
 (d) De un algoritmo divide y vencerás para multiplicar dos polinomios
    de grado n basándose en la fórmula del punto (c)