Tarea 4 de Análisis de Algoritmos

Trimestre 2007 Primavera
Entrega: 23 de julio de 2007 a las 10:00 am en la oficina H-264.

1. Demuestre que existen al menos O(2ⁿ) órdenes distintos en los que se puede llenar la tabla correspondiente a un algoritmo de programación dinámica para el problema de la multiplicación encadenada de n matrices.
   
2. Encuentre contraejemplos para cada uno de los siguientes tres algoritmos para el problema de la mochila: (a) meter los objetos en la mochila conforme van llegando, (b) meter primero los objetos más pequeños y (c) meter primero los más grandes. En cada caso, debe dar la solución entregada por el algoritmo y la solución óptima.
   
3. Demuestre que el siguiente problema llamado EXACTCOVER es NP-completo: Sean n y m dos enteros positivos y sean A₁, A₂, ..., A_m una colección de subconjuntos de {1, 2, ..., n}. ¿Existirá alguna subcolección de esos subconjuntos tal que cada elemento de {1, 2, ..., n} esté contenido en exactamente un miembro de la subcolección? Pista: Reduzca 3SAT a EXACTCOVER.