Final escrito de Min Chih Lin.

Enunciados

Ejercicio 1

Escribir un algoritmo que utilice la técnica de "programación dinámica" para calcular la subsecuencia creciente máxima de una secuencia de números (el mejor algoritmo conocido es de tiempo $O(n.log(n))$ y usa espacio $O(n)$ ). Mostrar la correctitud y determinar la complejidad del algoritmo propuesto.

Ejercicio 2

El grafo $Q_{d}$ , también llamado hipercubo de orden $d$ , se define inductivamente de la siguiente manera: $Q_{0}=K_{1}$ , y $Q_{d}$ con $d\in N_{>}0$ es el grafo que se obtiene al tomar dos copias de $Q_{d}-1$ y agrega un eje entre cada vértice de una copia y su vértice correspondiente en la otra copia. Por ejemplo $Q_{1}=K_{2}$ , $Q_{2}=C_{4}$ (ciclo simple de 4 vértices).