1.- Un aficionado propone la siguiente función para clasificar triángulos según sus lados. La salida debe ser 1, 2, ó 3 dependiendo si el triángulo es equilátero, isósceles, o escaleno respectivamente.

int triangle (int a, int b, int b) {
        if (a==b) {
                if (b==c)
                        return 1;
                else
                        return 2;
        }else if( b==c)
                return 2;
              else
                return 3;
}

2.- Demuestre que si f(n) es O(g(n)), entonces f(n)+c es aún O(g(n)) para cualquier constante c. Obs: g(n) > 1 para todo n.

3.- Asuma que f₁(n) < f₂(n) para todo n mayor que n_o, y que f₂(n) es O(g(n)). Demuestre que f₁(n)+f₂(n) es O(g(n)). Obs: g(n) > 1 para todo n.

4.- Ordene las siguientes funciones según su crecimiento asintólico. Use f(n) < g(n) si f(n) = o(g(n)); f(n) = g(n) si f(n) = Q (g(n)).

1. 3n²+3n +7
2. 5n (3 +log n)
3. (5n+4)/6
4. 1+2+3+4+...+n
5. n+ log n²
6. ((n+1)logn)/2

• Si n es par entonces A*xⁿ es lo mismo que A * (x²)^n/2. Por ello podemos reemplazar x por x² y n por n/2 y el valor de A*xⁿ será el mismo que el original.
• Si n es impar entonces A*xⁿ es lo mismo que (A*x)*(x²)^(n-1)/2. Por ello si A es actualizado por A*x, x es asignado x², y n es reemplazado por (n-1)/2, el valor de la expresión A*xⁿ será el mismo que el original.

6.- ¿Cuántas hojas tiene un árbol binario lleno de n nodos?

7.- Muestre el contenido resultante luego de aplicar buildHeap a

8.- Resuelva la recurrencia: T(n) = T(n/2) + c*n en términos asintóticos.

9.- Codifique la rutina insertionSort(LIST L) donde L es una lista doblemente enlazada con centinela.

10.- considere la siguiente implementación de partition:

int partition (int a[], int p, int r ) {
        int i=p-1, j=r; int pivote =a[r], aux;
        for (;;) {
                while(a[++i] < pivote) ;
                while( pivote < a[--j]) if (j==p) break;
                if (i>=j) break;
                aux=a[i];
                a[i]=a[j];
                a[j]=aux;
        }
        aux=a[i];
        a[i]=a[r];
        a[r]=aux;
        return i; 
}

¿Es este algoritmo estable?

11.- Considere que tiene una potencia de dos de datos. Muestre por qué el mejor caso para el problema de selección tiene costo de tiempo Q (n) y peor caso Q (n²).

12.- Haga la implementación de una cola usando la estructura de datos lista simplemente enlazada.