Exámenes
| Examen | Cuándo | Temas |
|---|---|---|
| Parcial | Semana 8 | Semanas 1–7: invariantes, matching estable, recurrencias, divide y vencerás, cotas inferiores, greedy, Huffman, Dijkstra, árboles de expansión mínima, DFS y las primeras ideas de programación dinámica |
| Final | Semana 16 | Todo el curso, con énfasis en las semanas 9–15: programación dinámica, caminos mínimos, flujo, reducciones, NP-completitud y problemas difíciles |
Formato sugerido
- Simular a mano: un algoritmo sobre una entrada pequeña, escribiendo su estado: tabla, red residual o cola de prioridad.
- Demostrar: una invariante, un argumento de intercambio o las dos direcciones de una reducción.
- Dar un contraejemplo: una regla greedy que parece buena y falla.
- Resolver una recurrencia: con el teorema maestro o con un árbol de recursión.
- Diseñar: dado un problema escrito en palabras, elegir la técnica, escribir el pseudocódigo, justificarlo y dar su costo.
- Reducir: modelar un problema como flujo, o demostrar que es NP-completo.
Cómo estudiar
- Las Preguntas de repaso al final de cada guía semanal.
- Los ejercicios al final de cada capítulo de los apuntes.
- Escribir cada demostración sin mirar los apuntes, y después compararla paso a paso.
- Ante un problema nuevo, decidir la técnica antes de escribir código.
- Rehacer los laboratorios y las prácticas sin mirar la solución.
- Resolver el final de práctica en unas dos horas, en papel, y al corregirlo recorrer su lista de resultados para el final: cada resultado de aprendizaje del curso, con las semanas y las preguntas que lo ejercitan.
Banco de preguntas
Guardar los enunciados aquí (parcial-1.md, final-1.md, …). Las soluciones no
deberían subirse a un repositorio público; usar exams/solutions/ (está en .gitignore).