CC30A Algoritmos y estructuras de datos

Clase Auxiliar 08/09/2000

Problema 1: Calcule el tiempo utilizado por el siguiente algoritmo:

int elevado(x,n){
    /* caso base */
    if (n == 0) {
        return 1;
    }
    /* caso recursivo impar*/
    else (n es impar) {
        return x * elevado(x,n-1);
    }
    /* caso recursivo par*/
    else (n es par) {
        return elevado(x*x,n/2);
    }
}

Problema 2: Calcule el tiempo utilizado por el siguiente algoritmo:

int sumaLista (lista l){
    if l.largo = 0
        return 0
    else l.largo = 1
        return l.primerElemento
    else sumaLista (l.mitadDerecha) + sumaLista (l.mitadIzquierda);
}

Supuestos:

Problema 3: Calcule el tiempo utilizado por el siguiente algoritmo:

lista Qsort(lista l){
    if l.length < 2
        return l
    else{
        pivote = l.elemDelMedio
        redistribuir los elementos de l de modo que los menores queden a la derecha del pivote y los mayores a la izquierda
        lDer= Qsort(l.derechaPivote);
        lIzq= Qsort(l.izquierdaPivote);
        return lDer.concatena(lIzq);
    }
}

Supuestos:

Problema 4: Resuelva la ecuación de recurrencia fn = 3fn-1 - 2fn-2 mediante:

f0 = 0
f1 = 1

   a.Planteando el polinomio característico

   b.Adivinando la serie, y demostrando su validez

Problema 5: Resuelva la ecuación de recurrencia fn = fn-1 - fn-2 planteando su polinomio característico.

f0 = 0
f1 = 1

Problema 6: Resuelva la ecuación de recurrencia T(n) = 2T(n/2) - 3T(n/4) + 7

T(1) = 1
T(2) = 2

Hint: realice un cambio de variables, elimine el termino constante y resuelva el polinomio característico.