Me lo contaron y lo olvidé; lo vi y lo entendía; lo hice y lo aprendí.

Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2023/2024

1. Análisis de algoritmos

Horas de clases presenciales: 8 (4 teoría + 4 prácticas)
Horas de trabajo no presencial: 8

Recursos

Complementa las clases estudiando los siguientes apartados del capítulo 5 "Análisis de Algoritmos" del libro "Estructuras de datos en Java" (2000) de M. A. Weiss:

La edición en castellano "Estructuras de datos en Java" (2013) contiene erratas que nos hacen descartarla.

Recursos opcionales

Si lo prefieres, puedes consultar la edición en inglés del mismo autor "Data structures and problem solving using Java" (2010). En su edición "Data Structures and Algorithm Analysis in C++" (2014) faltan algunos de los apartados recomendados.

Otra referencias opcionales que te pueden interesar si quieres profundizar en este tema o ver textos alternativos son:

Las siguientes referencias te pueden servir si quieres más información sobre el coste amortizado de duplicar la capacidad de un vector que se explicará en la última clase de teoría:

Introducción a los ejercicios

La sección "Ejercicios" contendrá en cada tema una propuesta de ejercicios a completar en el tiempo de trabajo de clase más el tiempo de trabajo no presencial de la asignatura.

No es obligatorio entregar las soluciones y no son puntuables, pero puedes pedir al profesor que revise lo que quieras y que te aclare cualquier duda, con el objetivo de aprender.

Puedes trabajar en pareja o en grupo si lo deseas, siempre que el objetivo sea que todos aprendáis a escribir las soluciones. Puedes pedir ayuda a otros estudiantes y comparar tu solución con las suyas.

Es importante no ver las soluciones antes de haber intentado resolver los ejercicios, porque debes aprender a escribirlas, no a leerlas.

Dedicaremos las primeras sesiones de laboratorio a adaptarnos a un nuevo lenguaje de programación (C++) y seguiremos introduciendo características de C++ poco a poco a lo largo del curso. Las soluciones en C++ que se proporcionan son también una ayuda para ir conociendo mejor el lenguaje.

Cada estudiante podrá decidir libremente con qué herramienta realizar todas las prácticas del curso. En clase veremos cómo trabajar usando Linux, empleando el compilador g++ y cualquier editor. También veremos cómo trabajar con Online GDB.

En los ejercicios 2 y 3 veremos también cómo realizar comparaciones experimentales de diferentes soluciones algorítmicas a un mismo problema, midiendo tiempos de ejecución para diferentes tallas del problema y observando cómo crece el tiempo de ejecución cuando crece la talla.

Algunos de los siguientes ejercicios requieren que sepas que existen algoritmos que permiten ordenar un vector en tiempo O(n log n). A lo largo del curso estudiaremos algunos de esos algoritmos:

De momento no necesitas saber más de ellos.

En tu tiempo de trabajo no presencial puedes resolver también los ejercicios del siguiente apartado Refuerzo de conceptos básicos: recursión. Te interesa mucho aprender a resolver esos ejercicios cuanto antes, si no sabes hacerlo ya.

Ejercicios

Primera parte: Conceptos básicos Septiembre

  1. Clase de prácticas LA2 12/09, LA1 y LA3 14/09

    Asegúrate de que entiendes estos tres ejemplos iniciales de C++, explicados en la primera sesión de prácticas.

    Prueba esto en un terminal tras guardarlos, para compilarlos y ejecutarlos:

    g++ ejemplo_for.cpp && ./a.out

    g++ ejemplo_vector.cpp && ./a.out

    g++ ejemplo_funcion.cpp && ./a.out

    En el tercer ejemplo se hace uso de C++11 para inicializar el vector. Si en tu ordenador tienes una versión de g++ más antigua que la que tenemos este curso en las aulas, es posible que tengas que informarle de que usas C++11:


    g++ ejemplo_funcion.cpp -std=c++11 && ./a.out

    Pueba a compilar los mismos ejemplos con Online GDB. En el resto del curso puedes seguir trabajando con él si lo prefieres.

  2. Clase de prácticas LA2 12/09, LA1 y LA3 14/09

    1. Implementa una función recursiva que calcule y devuelva el n-ésimo número de Fibonacci, pasándole n. Haz una primera versión aplicando directamente esta definición recursiva.

      Solución

    2. Resuelve el mismo problema con una función iterativa que obtenga cada número a partir de los dos anteriores.

      Utilíza ambas soluciones para calcular desde f0 hasta f50. Observa el tiempo que tardan en calcular cada nuevo número (en el apartado c verás cómo cronometrar ese tiempo con precisión) y la importante diferencia práctica entre ambas (de lo cual no puede deducirse que sea malo utilizar funciones recursivas: lo que hace tan lenta esa solución no es su naturaleza recursiva sino el hecho de estar repitiendo cálculos).

      Solución

    3. Consulta aquí el resultado de comparar experimentalmente las dos soluciones anteriores midiendo sus tiempos de ejecución.

      Nota sobre evaluación: Medir experimentalmente tiempos de ejecución no será materia de examen, aunque éste es un ejercicio importante para convencerte de la importancia práctica del contenido de la asignatura. Si no estás convencido de eso, lo puedes pasar mal estudiándola. Por otra parte, la comparación experimental de algoritmos te resultará útil cuando el análisis teórico no baste para elegir uno.

  3. Clase de prácticas LA2 12-19/09, LA1 y LA3 14-21/09

    1. ¿Conoces algún algoritmo, entre los que has estudiado en primer curso, que tenga coste temporal O(log n) en el peor caso? ¿Cuál es su coste temporal en el mejor caso?

    2. Implementa en C++ una función que reciba como argumentos un vector de enteros y un dato que queremos buscar en dicho vector. La función debe "devolver" (no lo confundas con "mostrar") la posición del dato si lo encuentra y -1 en caso contrario. Si el dato aparece más de una vez, debe devolver una (cualquiera) de las posiciones en que aparece.

      Hazlo empleando el algoritmo de búsqueda secuencial de forma no recursiva.

      Solución

      Aprende más ayudando a otros estudiantes

    3. Resuelve de nuevo el problema anterior empleando esta vez el algoritmo de búsqueda binaria de forma no recursiva (suponiendo que es un vector ordenado).

      Solución

    4. Clase de teoría TE1 14/09

      Después mira con detalle esta comparación experimental midiendo tiempos, que se analizará en clase de teoría. También la utilizaremos, en la siguiente clase de prácticas, para ver la importancia práctica de pasar los vectores por referencia.

  4. Sustituye la implementación no recursiva del algoritmo de búsqueda binaria del ejercicio 3.c por una implementación recursiva.

    Solución

    Aprende más ayudando a otros estudiantes

    1. Clase de teoría TE1 14/09

      Analiza el coste temporal, en el mejor y en el peor caso, de este algoritmo para buscar la posición de un dato en un vector de talla n (es la solución del ejercicio 3.a). Indica cuándo se dan el mejor y el peor caso.

      int busquedaSecuencial(const vector<int> & v, int dato) {
         for (int i = 0; i < v.size(); i++)
            if (v[i] == dato)
               return i;
         return -1;
      }
      		

      Solución

    2. Clase de teoría TE1 14/09

      Analiza el coste temporal, en el mejor y en el peor caso, de este algoritmo para sumar los datos de un vector de talla n. ¿Coinciden los resultados con los del apartado anterior? ¿Por qué?

      int sumar(const vector<int> & v) {
         int suma = 0;
         for (int i = 0; i < v.size(); i++)
            suma += v[i];
         return suma;
      }
      		

      ¿Cambiaría alguno de esos costes si implementásemos así el algoritmo?

      int sumar(const vector<int> & v) {
         if (v.size() == 0)
            return 0;
         if (v.size() == 1)
            return v[0};
         int suma = v[0];
         for (int i = 1; i < v.size(); i++)
            suma += v[i];
         return suma;
      }
      		

      Solución

    3. Clase de teoría TE1 21/09

      Analiza el coste temporal, en el mejor y en el peor caso, del algoritmo de ordenación por inserción.

    4. Analiza el coste temporal, en el mejor y en el peor caso, del algoritmo de ordenación por selección.

    5. Resuelve este ejercicio sobre costes temporales de bucles (incluye las soluciones).

  5. Clase de teoría TE1 21/09

    Averigua, consultando por ejemplo la página Sumatorio de la Wikipedia, cómo calcular estos sumatorios, que no debes confundir entre sí (en estos sumatorios se usa MathML, para verlos correctamente es recomendable utilizar alguna versión reciente de Firefox).

    i = 1 n i = 1 + 2 + + n i = 0 n 2 i = 2 0 + 2 1 + + 2 n

  6. Tenemos n ≥ 2 datos de tipo real almacenados en un vector y queremos encontrar, entre todos los posibles pares de datos, un par tal que la diferencia entre los dos valores del par sea mínima (por ejemplo, para emparejar a los dos jugadores que tienen la puntuación más similar en un videojuego). ¿Cómo resolverías el problema, y qué coste tendría, sin ordenar el vector? ¿Sería mejor ordenar primero el vector con un algoritmo de coste O(n2) y aprovechar después esa ordenación? ¿Sería mejor ordenarlo con un algoritmo de coste O(n log n) y aprovechar después esa ordenación? ¿Qué harías si no fuese posible modificar el vector y cómo afectaría eso al coste temporal?

    Solución

  7. Propón un algoritmo para averiguar en tiempo O(n log n) si dos vectores contienen los mismos datos y en las mismas cantidades, sabiendo que ambos son de talla n y no están necesariamente ordenados,

    Ayuda

    Solución

  8. Propón un algoritmo para averiguar en tiempo O(n log n) si un vector de talla n contiene elementos duplicados.

    Ayuda

    Solución

  9. Clase de prácticas LA2 19/09, LA1 y LA3 21/09

    Implementa una función recursiva que reciba un valor real x y un valor entero n y devuelva el resultado de calcular xn. Contempla la posibilidad de que el exponente sea negativo. Tu solución debe ejecutarse en tiempo O(log |n|).

    Ayuda

    Solución

    También es válida esta solución de M. A. Weiss (aunque en ella no trabaja con valores de tipo real). Puedes encontrar una explicación en el apartado 2.4.4 "Logarithms in the Running Time" (páginas 87-88) de su libro "Data Structures and Algorithm Analysis in C++" (2014). Puedes encontrar una explicación alternativa en el apartado 1.6 "Un ejemplo elaborado: exponenciación" del libro "Estructuras de datos, algoritmos y programación orientada a objetos" (1998) de G. L. Heileman y en la página "Exponenciación binaria" de la Wikipedia.

  10. Clase de prácticas LA2 19/09, LA1 y LA3 21/09

    En un vector v1 tenemos números ordenados de menor a mayor sin repetidos. En otro vector v2 tenemos números con esas mismas condiciones. Queremos contar cuántos números comunes tienen v1 y v2.

    1. Diseña un algoritmo eficiente para resolver ese problema e impleméntalo en C++, suponiendo que no puedes utilizar llamadas recursivas.

      Ayuda (mírala después de pensar la solución)

      Solución

      Aprende más ayudando a otros estudiantes

    2. Resuelve de nuevo el mismo problema recursivamente, sin utilizar ningún bucle.

      Solución

      Aprende más ayudando a otros estudiantes

  11. Tras completar el ejercicio 11, diseña un algoritmo eficiente para resolver el problema de mezclar dos vectores ordenados. Su entrada serán dos vectores de números reales, cada uno de los cuales estará ordenado de menor a mayor y podrá contener elementos repetidos. Su salida debe ser un nuevo vector que contenga todos los elementos de ambos vectores ordenados también de menor a mayor.

    Por ejemplo, si los vectores de entrada son [11, 22, 33.3, 33.3, 35] y [10, 33.3, 40] el resultado debe ser [10, 11, 22, 33.3, 33.3, 33.3, 35, 40].

    La solución de este problema será una subrutina del algoritmo de ordenación por mezcla mergesort, como veremos en el tema 5.2.

    1. Resuelve el problema sin utilizar recursión.

      Analiza el tiempo de ejecución de tu solución en el peor caso y exprésalo en notación O.

      Solución

    2. Resuelve el mismo problema sin utilizar ningún bucle, con el mismo coste temporal.

      Solución

  12. Tras completar el ejercicio 12 y entender las soluciones propuestas, indica qué problema resuelve el algoritmo siguiente y analiza su coste temporal en el peor caso.

    vector<float> misterio(const vector<float> & a, const vector<float> & b) {
       vector<float> c(a.size() + b.size());
       int i = 0, j = 0, k = 0;
       while ( i < a.size() ) {
          while ( j < b.size() && b[j] <= a[i] ) {
             c[k] = b[j];
             k++;
             j++;
          }
          c[k] = a[i];
          k++;
          i++;
       }
       while ( j < b.size() ) {
          c[k] = b[j];
          k++;
          j++;
       }
       return c;
    }
    	    

    Solución

  13. Supongamos que en un vector de cadenas A tienes los DNI de los clientes de tu empresa de videojuegos y en otro vector B tienes los DNI de los clientes que ya han comprado el último videojuego lanzado al mercado. En una campaña de marketing quieres obtener a partir de ellos un vector con los DNI de los clientes que no han comprado ese videojuego. Propón un algoritmo para resolver el problema y analiza su coste computacional en cada uno de los casos siguientes:

    1. si ninguno de los dos vectores está ordenado;

    2. si el vector A ya está ordenado y el B no;

    3. si el vector B ya está ordenado y el A no; y

    4. si ambos están ordenados.

    ¿Vale la pena invertir tiempo en ordenar los vectores inicialmente para resolver el problema cuando no están ordenados?

    Solución

  14. Tienes que encontrar un número secreto n que es entero positivo y no sabes en qué rango se encuentra. Cada vez que hagas un intento fallido te dirán si el número secreto es mayor o menor que el que has propuesto. Propón un algoritmo para encontrar el número secreto realizando O(log n) intentos.

    Solución

  15. Tienes n monedas, siendo n potencia de 2, y sabes que una de ellas es falsa y pesa menos que las demás. Para encontrarla dispones de una balanza de dos platillos, en los que puedes poner tantas monedas como quieras. Diseña un procedimiento que te permita encontrar la moneda falsa realizando O(log n) pesadas (la única operación cuyo coste nos interesa, por tanto, es la de usar la balanza para pesar; es lo que pasaría, por ejemplo, si hubiera que pagar una cantidad fija por cada pesada). Después modifícalo, si hace falta, para evitar la necesidad de que n sea potencia de 2.

    Balanza

    Solución

Segunda parte: Análisis de algoritmos recursivos Septiembre / Diciembre

Cuando un algoritmo realiza un bucle, su coste depende de cuántas iteraciones hace el bucle y cuánto cuesta cada iteración. Análogamente, cuando un algoritmo realiza llamadas recursivas, su coste dependerá de cuántas llamadas recursivas se hacen y cuánto cuesta cada llamada. En los siguientes ejercicios vas a analizar eso. Realízalos en el orden propuesto, la dificultad es creciente y cada ejercicio se apoya en lo aprendido en los anteriores.

  1. Clase de teoría TE1 21/09

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo iterativo para calcular el factorial de un número entero no negativo.

      int factorial(int n) {
         int resultado = 1;
         for (int i = 2; i <= n; i++)
            resultado = resultado * i;
         return resultado;
      }
      		

      ¿Cambiaría alguno de esos costes con la siguiente modificación?

      int factorial(int n) {
         if (n <= 1)
            return 1;	 
         else {	 
            int resultado = 1;
            for (int i = 2; i <= n; i++)
               resultado = resultado * i;
            return resultado;
         }
      }
      		

      Solución

    2. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para realizar el mismo cálculo:

      int factorial(int n) {
         if (n <= 1)
            return 1;
         else
            return n * factorial(n - 1);
      }
      		

      Solución

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si todas las cifras de un entero son pares.

      bool verificarCifrasPares(int n) {
         if (n == 0)
            return true;
         return n % 2 == 0 && verificarCifrasPares(n / 10);
      }
      		

      Ayuda: mira la página "¿Cuántas cifras tiene un número?" de Félix Rodríguez Díaz.

      Solución

    2. ¿Cómo cambiarían esos costes al poner los operandos del operador && en el orden contrario?

      bool verificarCifrasPares(int n) {
         if (n == 0)
            return true;
         return verificarCifrasPares(n / 10) && n % 2 == 0;
      }
      		

      Solución

  2. Clase de teoría TE1 14/12

    Torres de Hanoi - instrucciones Torres de Hanoi

    Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para resolver el problema de las Torres de Hanoi.

    void dimeComoMover(int cantidadDiscos, int origen, int destino) {
       if (cantidadDiscos == 1)
          cout << "Mueve un disco de la aguja " <<  origen
               << " a la aguja " << destino << endl;
       else {
          int auxiliar = 6 - origen - destino;
          dimeComoMover(cantidadDiscos - 1, origen, auxiliar);
          cout << "Mueve un disco de la aguja " <<  origen
               << " a la aguja " << destino << endl;
          dimeComoMover(cantidadDiscos - 1, auxiliar, destino);
       }
    }
    void resolverLasTorresDeHanoi(int cantidadDiscos) {
       dimeComoMover(cantidadDiscos, 1, 3);
    }
                

    Código de prueba en onlineGDB

    Solución

  3. Analiza el coste temporal y espacial, en el mejor y en el peor caso, de la siguiente solución alternativa del ejercicio 10. ¿Se pueden reducir esos costes?

    float potencia(float base, int exponente) {
       if (exponente < 0)
          return 1 / potencia(base, -exponente);
       if (exponente == 0)
          return 1;
       if (exponente % 2 == 1)
          return base
                 * potencia(base, exponente / 2)
                 * potencia(base, exponente / 2);
       return potencia(base, exponente / 2)
              * potencia(base, exponente / 2);
    }
    	    

    Solución

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si un dato aparece en un vector de talla n

      bool buscar(const vector<float> & v, float dato, int fin) {
         if (fin < 0)
            return false;
         if (v[fin] == dato)
            return true;
         return buscar(v, dato, fin - 1);
      }
      
      bool buscar(const vector<float> & v, float dato) {
         return buscar(v, dato, v.size() - 1);
      }
      		

      Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste del vector?

      Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

      bool buscar(vector<float> v, float dato, int fin) {
         if (fin < 0)
            return false;
         if (v[fin] == dato)
            return true;
         return buscar(v, dato, fin - 1);
      }
      
      bool buscar(vector<float> v, float dato) {
         return buscar(v, dato, v.size() - 1);
      }
      		

      Ayuda

      Solución

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si un dato aparece en un vector ordenado de talla n.

      bool buscar(const vector<float> & v, float dato, int inicio, int fin) {
         if (inicio <= fin) {
            int medio = (inicio + fin) / 2;
            if (v[medio] < dato)
      	 return buscar(v, dato, medio + 1, fin);
            else if (v[medio] > dato)
      	 return buscar(v, dato, inicio, medio - 1);
            else
      	 return true;
         }
         return false;
      }
      
      bool buscar(const vector<float> & v, float dato) {
         return buscar(v, dato, 0, v.size() - 1);
      }
      		

      Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste del vector?

      Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

      bool buscar(vector<float> v, float dato, int inicio, int fin) {
         if (inicio <= fin) {
            int medio = (inicio + fin) / 2;
            if (v[medio] < dato)
      	 return buscar(v, dato, medio + 1, fin);
            else if (v[medio] > dato)
      	 return buscar(v, dato, inicio, medio - 1);
            else
      	 return true;
         }
         return false;
      }
      
      bool buscar(vector<float> v, float dato) {
         return buscar(v, dato, 0, v.size() - 1);
      }
      		

      Solución

  4. Clase de teoría TE1 14/12

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si un dato aparece en un vector de talla n.

      bool buscar(const vector<float> & v, float dato, int inicio, int fin) {
         if (inicio > fin)
            return false;
         int medio = (inicio + fin) / 2;
         if (v[medio] == dato)
            return true;
         if (buscar(v, dato, inicio, medio - 1))
            return true;
         if (buscar(v, dato, medio + 1, fin))
            return true;
         return false;  
      }
      bool buscar(const vector<float> & v, float dato) {
         return buscar(v, dato, 0, v.size() - 1);
      }
      		

      Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste del vector?

      Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

      bool buscar(vector<float> v, float dato, int inicio, int fin) {
         if (inicio > fin)
            return false;
         int medio = (inicio + fin) / 2;
         if (v[medio] == dato)
            return true;
         if (buscar(v, dato, inicio, medio - 1))
            return true;
         if (buscar(v, dato, medio + 1, fin))
            return true;
         return false;  
      }
      bool buscar(vector<float> v, float dato) {
         return buscar(v, dato, 0, v.size() - 1);
      }
      		

      Solución

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para averiguar si un dato aparece en un vector ordenado de talla n.

      bool buscar(const vector<float> & v, float dato, int fin) {
         int medio = fin / 2;
         if (v[medio] > dato) {
            if (medio == 0)
               return false;
            return buscar(v, dato, medio - 1);
         }
         for (int i = medio; i <= fin; i++)
            if (v[i] == dato)
               return true;
         return false;
      }
      bool buscar(const vector<float> & v, float dato) {
         return buscar(v, dato, v.size() - 1);
      }
      		

      Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste del vector?

      Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

      bool buscar(vector<float> v, float dato, int fin) {
         int medio = fin / 2;
         if (v[medio] > dato) {
            if (medio == 0)
               return false;
            return buscar(v, dato, medio - 1);
         }
         for (int i = medio; i <= fin; i++)
            if (v[i] == dato)
               return true;
         return false;
      }
      bool buscar(vector<float> v, float dato) {
         return buscar(v, dato, v.size() - 1);
      }
      		

      Solución

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para buscar el máximo en un vector de talla n ≥ 1. Justifica brevemente tus respuestas.

      int maximo(const vector<int> & v) { // Suponiendo v.size() >= 1
         if (v.size() == 1) return v[0];
         vector<int> resto(v.size() - 1);
         for (int i = 1; i < v.size(); i++)
            resto[i - 1] = v[i];
         int maximoResto = maximo(resto);
         if (maximoResto > v[0])
            return maximoResto;
         else
            return v[0];
      }
      		

      Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste de los vectores?

      Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

      int maximo(vector<int> v) { // Suponiendo v.size() >= 1
         if (v.size() == 1) return v[0];
         vector<int> resto(v.size() - 1);
         for (int i = 1; i < v.size(); i++)
            resto[i - 1] = v[i];
         int maximoResto = maximo(resto);
         if (maximoResto > v[0])
            return maximoResto;
         else
            return v[0];
      }
      		

      Solución

  5. Clase de teoría TE1 14/12

    1. Analiza el coste temporal y espacial, en el mejor y en el peor caso, del siguiente algoritmo recursivo para buscar el máximo en un vector de talla n ≥ 1. Justifica brevemente tus respuestas.

      int maximo(const vector<int> & v) { // Suponiendo v.size() >= 1
         if (v.size() == 1) return v[0];
         int mitad = v.size() / 2;
         vector<int> izquierda(mitad);
         for (int i = 0; i < mitad; i++)
            izquierda[i] = v[i];
         vector<int> derecha(v.size() - mitad);
         for (int i = mitad, j = 0; i < v.size(); i++, j++)
            derecha[j] = v[i];
         int maximoIzquierda = maximo(izquierda);
         int maximoDerecha = maximo(derecha);
         if (maximoIzquierda >= maximoDerecha)
            return maximoIzquierda;
         else
            return maximoDerecha;
      }
      		

      Solución

    2. ¿Cuál es el coste espacial, en el mejor y en el peor caso, sin contar el coste de los vectores?

      Solución

    3. ¿Cuáles serían los 4 costes analizados en el apartado a si, sin cambiar nada más, el vector se pasase por valor en vez de por referencia?

      int maximo(vector<int> v) { // Suponiendo v.size() >= 1
         if (v.size() == 1) return v[0];
         int mitad = v.size() / 2;
         vector<int> izquierda(mitad);
         for (int i = 0; i < mitad; i++)
            izquierda[i] = v[i];
         vector<int> derecha(v.size() - mitad);
         for (int i = mitad, j = 0; i < v.size(); i++, j++)
            derecha[j] = v[i];
         int maximoIzquierda = maximo(izquierda);
         int maximoDerecha = maximo(derecha);
         if (maximoIzquierda >= maximoDerecha)
            return maximoIzquierda;
         else
            return maximoDerecha;
      }
      		

      Solución

Tercera parte: Coste amortizado Diciembre

  1. Clase de teoría TE1 14/12

    Considera la implementación del Tipo Abstracto de Datos Pila que puedes encontrar en esta carpeta (o en este enlace de OnlineGDB). En ella se utiliza internamente un vector para guardar los datos de la pila. En el método apilar, se duplica el tamaño de ese vector si está lleno. Para ello, se utiliza el método resize de la clase vector, cuyo coste temporal es O(n), siendo n el nuevo tamaño del vector.

    1. ¿Cuál es el coste temporal en el peor caso de ese método apilar?

    2. ¿Cuál es el coste temporal en el peor caso de realizar una secuencia de n operaciones apilar como las que se realizan en el siguiente fragmento de código?

      Pila p;		    
      for (int i = 1; i <= n; i++)
         p.apilar(10 * i);
      		  
    3. ¿Cuál es el coste amortizado del método apilar?

    Solución

  2. Un árbol biselado (splay tree) es un árbol binario de búsqueda en el que los algoritmos de inserción y eliminación son diferentes de los que hemos estudiado en el tema 3, consiguiendo tener coste amortizado O(log n) y coste en el peor caso O(n). Sin necesidad de saber cómo funcionan esos algoritmos, sabiendo que tienen esos costes, analiza cuál sería el coste temporal en el peor caso del algoritmo de ordenación del ejercicio 13 del tema 3 si sustituimos el árbol por un árbol biselado.

    void ordenar(vector<int> & v) {
    
       Multiconjunto multiconjunto;
    
       for (int dato : v)
          multiconjunto.insertar(dato);
    
       v = multiconjunto.obtenerOrdenados();
    
    }
    	      

    Solución

  3. Clase de teoría TE1 14/12

    Un montículo de Fibonacci es una estructura de datos que permite implementar colas de prioridad con estos costes temporales:

    Coste en el peor caso Coste amortizado
    Insertar O(1) O(1)
    ConsultarMínimo O(1) O(1)
    EliminarMínimo O(n) O(log n)
    DisminuirPrioridad O(n) O(1)

    Sin necesidad de conocer cómo funcionan los montículos de Fibonacci, teniendo en cuenta solamente esos costes, ¿cuál sería el coste temporal en el peor caso del algoritmo de Dijkstra si la cola de prioridad se implementase utilizando un montículo de Fibonacci? Recuerda el ejercicio 14 del tema 6.

    Solución

  4. Teniendo en cuenta la tabla de costes del ejercicio anterior, analiza el coste temporal en el peor caso del algoritmo de Huffman cuando se aplica a un alfabeto que tiene n caracteres, suponiendo que la cola de prioridad que utiliza el algoritmo se implementa empleando un montículo de Fibonacci. Recuerda el ejercicio 3 del tema 5.1.

    Solución

Refuerzo de conceptos básicos: recursión

En esta asignatura aparecerán con frecuencia algoritmos recursivos, en unas ocasiones deberás leerlos y entenderlos y en otras deberás escribirlos.

Si tienes dificultades para entender la recursión, estudia primero los apartados 10.1, 10.2 (exceptuando el ejemplo de análisis sintáctico) y 10.3 del capítulo 10 "Implementación de TADs: recursión, análisis de algoritmos y algoritmos estándar" del libro "TADs, estructuras de datos y resolución de problemas con C++" (2006) de L. R. Nyhoff.

El vídeo "What on Earth is Recursion?" de Computerphile te puede interesar también (observa que puedes ponerle subtítulos traducidos automáticamente al castellano si te hace falta).

Como refuerzo, resuelve de forma recursiva cada uno de los siguientes problemas (recuerda que debes aprender a escribir las soluciones, y eso es muy diferente de leer las soluciones).

  1. Contar las cifras de un entero no negativo n.
    Solución

  2. Contar las veces que una cifra c aparece en un entero no negativo n.
    Solución

  3. Averiguar si todas las cifras de un entero no negativo n son pares.
    Solución

  4. Averiguar si un dato d aparece en un vector v.
    Solución (versión 1) Solución (versión 2)

  5. Contar las veces que un dato d aparece en un vector v.
    Solución

  6. Mostrar en la salida estándar los elementos de un vector v en orden natural, del primero al último, uno en cada línea.
    Solución

  7. Mostrar en la salida estándar los elementos de un vector v en orden inverso, del último al primero, uno en cada línea.
    Solución

  8. Averiguar si un vector no vacío v está ordenado de menor a mayor.
    Solución (versión 1) Solución (versión 2)

  9. Encontrar el menor elemento en un vector no vacío v.
    Solución

  10. Averiguar si todos los elementos de un vector no vacío v son mayores que un dato d.
    Solución (versión 1) Solución (versión 2)

El tiempo invertido debería ser parte de las 300 horas de programación de primer curso.

Autoevaluación

Tras completar el trabajo del tema 1 deberías ser capaz de resolver los siguientes ejercicios de los exámenes del curso pasado.