Final de práctica — Análisis y Diseño de Algoritmos

Temas: todo el curso, con énfasis en las semanas 9 a 15 · Tiempo de trabajo estimado: 120 minutos

Este es un examen de práctica con el formato del final. Sirve para medir cuánto les toma cada tipo de pregunta: resuélvanlo en papel, con el reloj corriendo, y recién después comprueben sus respuestas con los programas de cada semana. Cada pregunta trae su tiempo estimado.

Indicaciones

• Escriban el procedimiento, no solo el resultado: es lo que después van a comparar paso a paso. Si un inciso usa un resultado anterior que les salió mal, sigan con su número.
• Una demostración dice primero qué afirma y qué técnica usa, y después va por pasos cortos, como en los apuntes.
• En pseudocódigo importa la idea. Usen el formato del curso o uno parecido.

Convenciones del curso

• Grafos: los nodos se numeran desde 0, salvo en la red de flujo, que usa letras. ∞ quiere decir que no hay camino.
• Dijkstra: el de la semana 5. Fija un nodo al sacarlo del heap y no vuelve a relajar sus aristas.
• Bellman-Ford: d_i(v) es el menor largo de un camino de s a v con a lo sumo i aristas. La versión de una sola fila relaja las aristas en el orden de la lista, y se detiene después de una vuelta que no cambia nada.
• Floyd-Warshall: d_k(i, j) permite como intermedios solo a los nodos 0, …, k − 1. En cada matriz, la fila es el origen y la columna el destino.
• Edmonds-Karp: BFS en la red residual. De cada nodo se revisan los vecinos en orden alfabético (a, b, c, d, t), así que entre dos caminos igual de cortos gana el que se descubre antes. Un arco inverso se escribe ⇒.
• Cadena de matrices: la matriz Aᵢ mide d[i] × d[i + 1].

Parte A — Repaso de la primera mitad

Pregunta 1 — Recurrencias

Tiempo estimado: 8 min

Den el orden Θ de cada recurrencia, con T(n) = Θ(1) para n pequeño. Si aplica el teorema maestro, digan qué caso es y comprueben lo que ese caso pide. Si no aplica, digan por qué y resuélvanla con un árbol de recursión.

a) T(n) = 4 T(n/2) + n²

b) T(n) = 3 T(n/4) + n

c) T(n) = 2 T(n/2) + n log n

d) T(n) = T(n/5) + T(7n/10) + n. ¿De qué algoritmo del curso es esta recurrencia? Con grupos de 3 en vez de 5, la recurrencia pasa a ser T(n) = T(n/3) + T(2n/3) + n. ¿Qué orden tiene, y qué diferencia entre las dos se ve en el árbol de recursión?

Pregunta 2 — Greedy: árbol mínimo e intervalos con pesos

Tiempo estimado: 10 min

a) Un grafo no dirigido de 6 nodos tiene estas aristas, con el peso entre paréntesis:

0-1 (4)   0-2 (1)   1-2 (3)   1-3 (2)   2-3 (5)
2-4 (8)   3-4 (6)   3-5 (9)   4-5 (7)   1-5 (10)

1. Corran Kruskal. Por cada arista que revisan, digan si entra o se descarta, y por qué. ¿Cuánto pesa el árbol?
2. ¿Cuál es la arista más liviana que cruza el corte {0, 1, 2, 3} | {4, 5}? ¿Qué dice de ella la propiedad del corte?
3. Si el peso de 4-5 sube a 11, ¿qué arista la reemplaza, y cuánto pesa el árbol nuevo?

b) Un aula recibe seis pedidos de clases, cada uno con un intervalo semiabierto [s, f) y un valor v:

[1,7) v9   [0,5) v4   [7,11) v7   [5,6) v8   [10,12) v2   [6,10) v3

1. Ordénenlos por hora de fin, y calculen p(j) y T[j] para j = 0, …, 6, con la recurrencia de la semana 7. ¿Qué clases se eligen?
2. ¿Cuánto da la regla “la que termina antes” de la semana 4? ¿Y “mayor valor primero”?
3. ¿En qué paso se rompe, con pesos, el argumento de intercambio que demostraba “la que termina antes”?

Parte B — Programación dinámica

Pregunta 3 — Cadena de matrices

Tiempo estimado: 10 min

Hay que multiplicar cuatro matrices, con d = 4, 10, 3, 12, 5. Es decir, A₀ mide 4 × 10, A₁ mide 10 × 3, A₂ mide 3 × 12 y A₃ mide 12 × 5.

a) Escriban el subproblema M(i, j) en una frase y su recurrencia. ¿En qué orden se llena la tabla, y por qué ese orden sirve?

b) Llenen la tabla. Para M(0, 3), escriban la opción de cada k. ¿Cuál es el mínimo, y con qué parentización?

c) ¿Cuánto cuesta hacer siempre primero la multiplicación vecina más barata? ¿En qué paso se equivoca?

d) Alguien llena la tabla con i de menor a mayor y, dentro, j de menor a mayor, con la tabla empezando en ceros. ¿Qué casillas lee antes de llenarlas, y qué respuesta da?

Pregunta 4 — Conjunto independiente en un árbol

Tiempo estimado: 10 min

Este árbol tiene raíz 0. Cada línea dice los hijos de un nodo, y la segunda tabla, el valor de cada nodo:

0: 1 2      1: 3 4      2: 5      4: 6      5: 7 8      (3, 6, 7 y 8 son hojas)

nodo    0  1  2  3  4  5  6  7  8
valor   3  7  4  2  5  6  6  4  3

Se busca un conjunto independiente de suma máxima: nodos sin aristas entre ellos, es decir, sin un padre y un hijo a la vez.

a) Definan Con(v) y Sin(v) y escriban sus dos fórmulas. ¿Por qué hace falta más de un número por nodo?

b) Llenen la tabla de abajo hacia arriba. ¿Cuál es el valor óptimo? Reconstruyan el conjunto de arriba hacia abajo.

c) ¿Cuánto da el greedy “el de mayor valor primero, si no choca con un vecino ya elegido”? ¿Por qué esta programación dinámica no sirve en un grafo con ciclos, y qué dice el curso de ese problema en un grafo cualquiera?

Parte C — Caminos mínimos

Pregunta 5 — Bellman-Ford

Tiempo estimado: 12 min

Un grafo dirigido de 5 nodos tiene estas aristas, en este orden. El origen es 0.

0->1 (6)   0->2 (7)   1->3 (5)   1->4 (-4)   2->3 (-3)   2->4 (9)   3->1 (-2)   4->3 (7)

a) Corran Dijkstra. Escriban el orden en que fija los nodos y la distancia que tiene cada uno al fijarse. ¿Cuáles se fijan con un valor equivocado, y en qué momento falla la idea de fijar? Al terminar, ¿qué nodo queda mal en el arreglo de distancias, y por qué?

b) Llenen la tabla d_i(v) para i = 0, …, 4. Sigan a mano dos casillas que cambian.

c) Corran la versión de una sola fila, con las aristas en el orden de la lista. Escriban d después de cada vuelta. ¿Cuántas vueltas hace? ¿Es d después de la vuelta 1 igual a la fila d_1 de la tabla? ¿Qué afirma el teorema de la semana 10 sobre esa relación?

d) Ahora el peso de 4->3 baja de 7 a 1. ¿Qué ciclo negativo aparece, y cuánto pesa? ¿Cómo se entera Bellman-Ford? ¿Para qué nodos deja de existir δ(v), y para cuáles sigue existiendo?

Pregunta 6 — Floyd-Warshall

Tiempo estimado: 8 min

Un grafo dirigido de 4 nodos tiene estas aristas:

0->1 (3)   0->3 (9)   1->2 (-2)   2->0 (4)   2->3 (5)   3->1 (1)

a) Escriban d_0. Luego, para k = 0, 1, 2 y 3, digan qué casillas cambian al permitir el nodo k y con qué valor. Escriban la matriz final.

b) ¿Cómo saben, mirando las matrices, que este grafo no tiene ciclos negativos?

c) Un grafo tiene V = 2000 nodos, E = 10 000 aristas y pesos no negativos, y se piden las distancias entre todos los pares. Comparen Floyd-Warshall con correr Dijkstra desde cada nodo: den el orden de cada uno y una cuenta aproximada. ¿Cuál conviene? ¿Y si el grafo fuera denso, con E cerca de V²?

Parte D — Flujo

Pregunta 7 — Edmonds-Karp y el corte mínimo

Tiempo estimado: 15 min

Esta red va de s a t. Las capacidades van entre paréntesis:

s->a (6)   s->b (7)   a->c (7)   a->d (3)   b->a (1)
b->c (9)   c->t (7)   d->c (5)   d->t (7)

a) Corran Edmonds-Karp con la convención de la portada. Por cada vuelta, escriban el camino, su cantidad de aristas, el cuello de botella y el valor acumulado. Marquen los arcos inversos.

b) Escriban el flujo final de cada arista.

c) ¿Qué nodos se alcanzan desde s en la red residual final? Escriban el corte que forman, sus aristas y su capacidad. ¿Por qué eso demuestra que el flujo es máximo, sin probar otros flujos?

d) Nombren una arista saturada que no cruza ese corte.

e) En la primera vuelta hay varios caminos igual de cortos. ¿Cuáles? Con otro desempate, ¿podrían cambiar los caminos? ¿Y el valor final?

Pregunta 8 — Selección de proyectos

Tiempo estimado: 12 min

Una empresa decide qué construir este año. Cada proyecto tiene una ganancia, negativa si es un costo, y algunos requieren otros:

proyecto    ganancia   requiere
tienda          6      servidor
app             8      servidor, api
pagos           5      api, licencia
chat            2      app
servidor       -7
api            -6
licencia       -6

a) Una idea es revisar cada proyecto con ganancia, junto con todo lo que requiere, y hacerlo si ese paquete solo deja ganancia. ¿Qué elige, y cuánto gana?

b) Construyan la red de la semana 12: nodos, aristas y capacidades. En un programa, ¿qué número usarían como infinito, y por qué ese basta?

c) Encuentren un corte mínimo. Den su capacidad, las aristas que lo cruzan y qué significa cada una. ¿Cuál es la ganancia máxima, y qué proyectos se eligen?

d) Si las aristas de requisito tuvieran capacidad 1, ¿qué ganancia diría la cuenta y qué conjunto leería? ¿Qué dirección de la demostración se rompe?

Parte E — Problemas difíciles

Pregunta 9 — Reducciones y NP-completitud

Tiempo estimado: 15 min

a) Apliquen la reducción de 3-SAT a conjunto independiente de la semana 14 a esta fórmula:

φ = (x1 ∨ ¬x2 ∨ x3) ∧ (¬x1 ∨ x2 ∨ ¬x3) ∧ (x1 ∨ x2 ∨ ¬x3)

Numeren los nodos de 0 a 8, cláusula por cláusula y en el orden en que aparecen los literales.

1. Escriban las aristas entre literales opuestos. ¿Cuántas aristas tiene el grafo en total, y qué k se pide?
2. Den un conjunto independiente de tamaño k que contenga al nodo 4. Lean la asignación que da, y comprueben que cumple φ.
3. A partir de la asignación x1 = V, x2 = F, x3 = F, construyan el conjunto independiente de la dirección de ida.

b) 4-coloreo pregunta si un grafo se puede colorear con cuatro colores. Demuestren que es NP-completo, con una reducción desde 3-coloreo. Sigan la receta del curso: en NP, la transformación, las dos direcciones y el tiempo.

c) Alguien escribe: “Reduje 4-coloreo a SAT, con una variable por cada nodo y cada color, así que 4-coloreo es NP-difícil”. ¿Qué está mal? ¿Qué demuestra en realidad esa reducción?

Pregunta 10 — Cobertura de vértices aproximada

Tiempo estimado: 10 min

Un grafo no dirigido de 8 nodos tiene estas aristas, en este orden:

0-1   2-3   1-2   4-5   3-4   5-6   6-7   1-5   2-6

a) Corran cobertura_por_matching de la semana 15 con las aristas en ese orden. Escriban el matching M, la cobertura C y su tamaño.

b) Encuentren una cobertura de 4 nodos. Usen M para demostrar que no existe una de 3, sin probar todos los subconjuntos.

c) El algoritmo dio exactamente el doble del óptimo. ¿Contradice eso el teorema? Corran el algoritmo otra vez, revisando primero 1-2 y 5-6 y después las demás en el orden de la lista. ¿Qué tamaño da?

d) Si el grafo fuera un árbol, ¿qué harían en lugar de aproximar, y con qué costo?

Parte F — Elegir la técnica

Pregunta 11 — Cinco problemas

Tiempo estimado: 10 min

Para cada problema, digan qué técnica usarían, de qué semana, y su costo con los tamaños dados. Supongan unos 10⁸ pasos simples por segundo y un límite de 1 segundo: ¿cabe? Digan además si el resultado cabe en int, que llega hasta 2 147 483 647, o si hace falta long long.

a) Contar cuántos pares i < j de un arreglo de n = 2 × 10⁵ números cumplen a[i] > a[j].

b) Un proyecto tiene 10⁵ tareas y 3 × 10⁵ dependencias, sin ciclos. Pasar de una tarea a otra que depende de ella tiene un costo entre −10⁵ y 10⁵, negativo cuando hay un bono. Se pide el camino de menor costo desde la tarea inicial hasta cada tarea.

c) Una fórmula con 10⁵ variables y 3 × 10⁵ cláusulas de dos literales cada una. ¿Se puede cumplir?

d) Un barrio tiene 40 cruces y 90 calles, y se quiere poner cámaras en la menor cantidad de cruces para que toda calle tenga una cámara en alguno de sus dos extremos.

e) Una mochila con n = 100 objetos, capacidad W = 50 000 y valores de hasta 10⁹. ¿Por qué este caso no contradice que la mochila sea NP-completa?

Lista de resultados para el final

Al corregir su práctica, marquen lo que ya pueden hacer. Cada línea es un resultado de aprendizaje del programa del curso, con las semanas donde se enseña y las preguntas de este final que lo ejercitan. Si una línea queda sin marcar, vuelvan a esas semanas y rehagan esas preguntas sin mirar los apuntes.

• Puedo demostrar que un algoritmo es correcto con una invariante, con inducción o con un argumento de intercambio. Semanas 1, 2, 4, 5 y 7. Preguntas 2 b), 3 a), 4 a), 5 c) y 7 c).
• Puedo plantear la recurrencia del costo de un algoritmo recursivo y resolverla con el teorema maestro o con un árbol de recursión. Semanas 2 y 3. Preguntas 1 y 11 a).
• Puedo diseñar un algoritmo con divide y vencerás, greedy o programación dinámica, justificar por qué la técnica sirve y dar un contraejemplo cuando una regla greedy falla. Semanas 2 a 5, 7, 9 y 10. Preguntas 2, 3, 4 y 11.
• Puedo modelar un problema escrito en palabras como un problema de grafos o de flujo. Semanas 5, 6, 10 y 12. Preguntas 8, 11 b) y 11 c).
• Puedo seguir a mano y demostrar Kruskal, Prim, Dijkstra, Bellman-Ford, Floyd-Warshall, las componentes fuertemente conexas y Ford-Fulkerson con Edmonds-Karp. Semanas 5, 6, 10 y 11. Preguntas 2 a), 5, 6, 7 y 11 c).
• Puedo implementar en C++ una solución que cumpla los límites de tiempo, usando la biblioteca estándar. Laboratorios de las semanas 1 a 7 y 9 a 15. En papel: preguntas 6 c) y 11, que estiman el tiempo y eligen entre int y long long. El resto se practica en los laboratorios.
• Puedo demostrar que un problema es NP-completo con una reducción, con sus dos direcciones, y explicar qué significa eso en la práctica. Semanas 13 y 14. Preguntas 9 y 11 e).
• Puedo elegir una estrategia para un problema difícil: un caso especial, búsqueda con poda, aproximación o un solucionador. Semanas 9, 13, 14 y 15. Preguntas 10 y 11 d).