Final del 20/12/19 (Algoritmos III)

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).

a) Determinar los valores de $d$ para los cuales $Q_{d}$ es planar. Justificar.

b) Determinar $\chi (Q_{d})$. Justificar.