Hoja de ejercicios de Algoritmos y complejidad con soluciones

¿Cuáles son los tres pasos de un algoritmo de divide y vencerás?

1. ADividir, vencer, combinar
2. BLeer, calcular, escribir
3. CAdivinar, comprobar, repetir
4. DOrdenar, buscar, devolver

Un problema suele llamarse tratable si:

1. APuede resolverse en tiempo constante
2. BNo tiene solución
3. CSolo puede resolverse probando todas las posibilidades
4. DPuede resolverse en tiempo polinómico

¿Qué describe el tiempo de ejecución en el caso promedio?

1. AEl tiempo esperado según una distribución dada de las entradas de tamaño n
2. BEl valor intermedio entre los tiempos de ejecución del mejor y del peor caso
3. CEl tiempo en el ordenador más común
4. DEl tiempo para una entrada de longitud media

¿Cuál es la complejidad temporal de quicksort en el peor caso?

1. AO(n log n)
2. BO(log n)
3. CO(n²)
4. DO(n)

¿Cuántos niveles tiene la recursión de merge sort para un array de n elementos?

1. AUnos n
2. BUnos n / 2
3. CUnos log₂ n
4. DUnos √n

¿Cómo construye el algoritmo de Prim un árbol de expansión mínima?

1. AEjecuta una búsqueda en anchura y se queda con el árbol BFS
2. BElimina la arista más cara hasta que no quedan ciclos
3. CHace crecer un único árbol desde un vértice inicial, añadiendo la arista más barata que sale del árbol
4. DOrdena todas las aristas por peso y añade cada una salvo que forme un ciclo en el bosque

El algoritmo de Strassen multiplica matrices usando 7 multiplicaciones recursivas de bloques de la mitad de tamaño en lugar de 8. ¿Cuál es su tiempo de ejecución?

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n² log n)
4. DΘ(n^{log₂ 7}), aproximadamente n^2,81

El problema de la mochila 0/1 resuelto con programación dinámica requiere un tiempo O(nW). ¿Por qué se llama pseudopolinómico?

1. AW es un número, así que el tiempo es exponencial en el número de bits empleados para escribir W
2. BPorque solo funciona para W = 0
3. CPorque el algoritmo es aleatorizado y su tiempo de ejecución varía con cada entrada
4. DPorque n siempre es pequeño