Ejercicios

[recusion, stacks] Entender el costo que implica usar el runtime stack. Bajo igualdad condiciones, ¿qué implementación requiere más memoria al ser ejecutada: una implementación iterativa o una recursiva?

[análisis de recursión] Determina el output de foo(0,5). Analiza su complejidad.

void foo(int n, int m  {
  if (n < m) {
    for (int i = 0; i < m; i++) {
        if (i > n) cout << "*";
        else       cout << " ";
    }
  }
}

[infix, postfix] Convierte la siguiente expresión a postfix: 3 * ((7 + 8) / 5)

[árboles binarios] Dado un puntero a nodo de arbol binario, determina si es una lista enlazada, i.e. todo nodo tiene un solo hijo. A continuación, dos ejemplos.

[heap] Añadir al heap una member function decrementElement(int i) que decremente el elemento indice i (y ajuste la estructura para que siga siendo heap). La siguiente figura muestra el heap inicial y luego de que elemento indice 2 ha sido decrementado por 12.

[complejidad recursiva] Determina la complejidad de fah. La función partition devuelve un índice entre low y high y requiere exactamente $n$ pasos, donde $n = high - low + 1$

int fah(int A[], int low, int high, int kth) {
    int i;
    i = partition(A[], low, high);
    if (i == kth)     return A[i];
    else if (i > kth) fah(A, low, i-1);
    else              fah(A, i+1, high);
}

[stacks y queues] Dado un queue de letras minúsculas (no espacios, ni mayúsculas, ni otros símbolos) usa un stack para determinar si el contenido del queue es un palíndromo. A continuación un queue de letras minúsculas que contiene un palíndrom.

[vector] Dado dos strings de letras minúsculas, determina si son anagramas en tiempo $O(n)$. https://es.wikipedia.org/wiki/Anagrama

[queue] Dado un queue con números enteros positivos, ordénalo ascendentemente usando solo otros queues y alguna que otra variable sencilla.

[bst sort] Dada la implementación de un BST usando nodos, añade la función bstSort que devuelve un arreglo de los elementos del BST en orden ascendente.

[priority queue] Supón que deseamos hallar el k-esimo número más grande de un arreglo. Dos formas posibles son:

• Ordenar los elementos usando algun algoritmo de sort y devolver el k-esimo elemento.
• Declarar un min priority queue PQ de tamaño k. Insertar los primeros k elementos de A en PQ. Para cada uno del el resto de los elementos del arreglo, si es mayor que la raiz de PQ: remover la raiz e insertar el elemento. El resultado al final está en la raiz.

Presenta un argumento usando complejidad para explicar por qué el segundo método es más eficiente.

[grafos] Dado la implementación de un grafo implementar un member funcion que dado un nodo devuelva todos los elementos que están a distancia 2.

[grafos] Dado la implementación de un grafo implementar un member funcion que determine el max indegree.

[grafos] Un nodo amigable es aquel que tal que tiene al menos $\frac{|V|}{2}$ otros nodos apuntando hacia él. Añade un member function al grafo que determina si un nodo es amigable.

[grafos] Dado la implementación de un grafo implementar un member funcion que determine el diámetro del grafo http://mathworld.wolfram.com/GraphDiameter.html

[árboles binarios] Dado un arreglo basado implementar funciones para determinar:

• si es un heap
• si es un BST
• si está balanceado
• su altura
• si es completo

[grafos] El complemento de un grafo G es un grafo con sus mismos nodos pero que solo tiene las aristas que G no tiene. Por ejemplo, un grafo y su complemento.

Añada un member function complement() a la clase grafo que devuelva su grafo complemento.

[sorting] Dado un arreglo saber ilustrar como se ordena usando mergesort y quicksort.

[heap] Saber aplicar las operaciones de percolate down, percolate up y heapify sobre un arreglo.