2019-2
Información general
Profesores
- Camilo Rocha (camilo.rocha *at* javerianacali.edu.co)
- Miguel Romero (miguel.romero *at* javerianacali.edu.co)
Horario
- Martes (Palmas - 3.2) 09:00 - 11:00
- Jueves (Palmas - 3.2) 09:00 - 11:00
Atención a estudiantes
- Lunes 10:00 - 12:00 (FIC 2-38)
- Lunes 14:00 - 16:00 (CRAI, 2do piso)
- Martes 11:00 - 11:45 (FIC 2-38)
- Miércoles 08:00 - 10:00 (CRAI, 2do piso)
Monitor Juan Esteban Cardona García (juanestebancg *at* javerianacali.edu.co)
- Monitoría: Viernes 11:00 - 13:00 (Palmas - 3.2)
Material
Examen final
- Fecha: noviembre 19 de 2019
- Horario: 09:00 - 11:00
- Salón: El Lago 2.2
Vínculos
- Arena de programación (tareas prácticas y proyecto)
- Notas (actualizado 11/22)
Tareas
- Tarea 1: semanas 1 y 2 (para entregar 08/02 y 08/04)
- Tarea 2: semanas 3 y 4 (para entregar 08/16 y 08/18)
- Tarea 3: semanas 6 y 7 (para entregar 09/10 y 09/11)
- enunciado
- casos de prueba
- reporte
- board final
- Tarea 4: semanas 8 y 9 (para entregar 09/24 y 09/29)
- Tarea 5: semanas 11 y 12 (para entregar 10/22)
- Tarea 6: semanas 15 y 16 (para entregar 11/08)
Sesiones
- Sesión 1 (07/23)
- Diseño y análisis de algorítmos
- Dividir y conquistar
- mergesort.py
- Sesión 2 (07/25)
- Sesión 3 (07/30)
- Dividir y conquistar
- Programación dinámica
- Sesión 4 (08/01)
- Sesión 5 (08/06)
- Longest Increasing/Decreasing Subsequence (LIS/LDS)
- apuntes de clase (LIS, 2016-2)
- apuntes de clase (LIS, 2017-2)
- código por memorización (LIS)
- código por tabulación (LIS/LDS)
- El problema del morral (Knapsack 0-1)
- Longest Increasing/Decreasing Subsequence (LIS/LDS)
- Sesión 6 (08/08)
- Rod Cutting
- Sesión 7 (08/13)
- Sesión 8 (08/15)
- Sesión 9 (08/20)
- Repaso
- Sesión 10 (08/22)
- Parcial 1
- Sesión 11 (08/27)
- Algoritmos voraces/avaros
- El problema del máximo agendamiento de actividades
- Sesión 12 (08/29)
- El problema del cubrimiento mínimo de intervalos
- Sesión 13 (09/03)
- El algoritmo de agendamiento de Johnson
- Sesión 14 (09/05)
- El algoritmo de agendamiento de Johnson
- Sesión 15 (09/10)
- Sesión 16 (09/12)
- Árboles de cubrimiento mínimo y el algoritmo de Kruskal
- código (incluye conjuntos disyuntos)
- Montones binarios minimales
- Árboles de cubrimiento mínimo y el algoritmo de Kruskal
- Sesión 17 (09/17)
- Montones binarios minimales
- Notas de clase
- Implementación con arreglos con capacidad variable (clase minheap)
- Montones binarios minimales
- Sesión 18 (09/19)
- Demostración de corrección del algoritmo de Kruskal (autor: Miguel Romero; incluye el Algoritmo de Bellman-Ford-Moore)
- Sesión 19 (09/24)
- Sesión 20 (09/26)
- Repaso
- Sesión 21 (10/01)
- Parcial 2
- Sesión 22 (10/03)
- Introducción a la teoría de complejidad
- problemas computacionales de decisión
- decibilidad vs. indecibilidad
- La clase P
- Introducción a la teoría de complejidad
- Sesión 23 (10/08)
- Propiedades de clausura de la clase P
- Sesión 24 (10/10)
- Sesión 25 (10/15)
- La clase NP-Complete
- Problemas NP-completos
- Clique es NP-Completo
- 3-CNF-SAT <=p Clique
- Sesión 26 (10/17)
- TSP es NP-Completo
- Hamiltonean-Path <=p TSP
- TSP con porgramación dinámica
- TSP es NP-Completo
- Sesión 27 (10/22)
- Si 2-Partition es NP-Completo, entonces 3-Partition es NP-Completo
- Sesión 28 (10/24)
- Sesión 29 (10/29)
- Algoritmos de aproximación
- 2-Approx para Vertex-Cover
- Sesión 30 (10/31)
- Sesión 31 (11/04)
- Bin-Packing
- k-Centers
- Sesión 32 (11/06)
- Cierre del curso
Exámenes pasados
- 2016-1: parcial 1, parcial 2, examen final
- 2016-2: parcial 1, parcial 2, examen final
- 2017-1: parcial 1, parcial 2, examen final
- 2017-2: parcial 1, parcial 2, examen final
- 2018-1: parcial 1, parcial 2, examen final
- 2018-2: parcial 1, parcial 2, examen final
- 2019-1: parcial 1, parcial 2, examen final
Proyecto
Christmas Lights: enunciado | arena | casos de prueba
- Entrega 0 (10%): ...
Esta entrega consta de un documento que describe la naturaleza de la solución del problema. En este documento se debe reflejar qué tanto entiende del problema, cuál es su estrategia de solución y la cantidad de trabajo que ha hecho para el proyecto. En esta entrega no es necesario tener una solución del problema pero sí tener claro cómo se puede resolver.
El documento para esta entrega no tendrá más de 3 páginas y, como mínimo, deberá contener la siguiente información:
- Especificación del problema (entrada y salida)
- Algoritmos y estructuras de datos que usará su solución (cada decisión debe ser justificada)
- Estrategia de solución
- Análisis (alto nivel) de complejidad temporal y espacial de su solución
- De ser necesario, citas bibliográficas del material consultado y que será usado en la solución del proyecto
Recuerde que el proyecto es individual.
- Entrega 1 (30%): ...
Esta entrega consta de un único archivo fuente en el lenguaje de programación Python que debe ser aceptado en la arena como correcto en la arena disponible para el proyecto.
El contenido del archivo debe contar con:
- Un encabezado que declare de forma unívoca la autoría del código: (i) nombre del autor (estudiante quien entrega el proyecto), (ii) su código de estudiante y (iii) la frase de compromiso del código de honor del curso.
- Documentación de cada una de las funciones usando el estándar de Python.
Cualquier archivo entregado sin seguir los lineamientos anteriores será ignorado para efecto de la calificación del proyecto.
- PR-A (1 segundo)
- Entrega 2 (60%): ...
Esta entrega consta de dos partes: (i) solución de casos de prueba y (ii) sustentación.
Los casos de prueba están clasificados como fáciles (PR-B), medios (PR-C) y difíciles (PR-D). Para obtener una puntación perfecta en esta entrega es indispensable que una solución resuelva correctamente todos los casos de prueba disponibles en la arena para PR-B, PR-C y PR-D. Para que una solución sea considerada para puntuar es necesario que el archivo cumpla con las condiciones de la Entrega 1. Tenga en cuenta también que los casos de prueba deben ser resueltos por la misma solución, es decir, no es posible usar dos soluciones distintas para los casos de prueba.
Adicionalmente, para esta entrega se evaluarán durante la sustentación los siguientes requisitos no funcionales:
- Diseño y uso clases para abstraer elementos de la solución
- Nombres de variables, funciones/metodos, etc. en inglés
- Elegancia del código
La sustentación de cada proyecto tomará alrededor de 10 minutos y para ello se abirará una lista de turnos. Para la sustentación es importante estar en capacidad de explicar la estrategia de solución, explicar los algoritmos utilizados (de memoria), describir las estructuras de datos utilizadas, y complejidades temporal y espacial de la solución. Una sustentación insatisfactoria del proyecto puede anular cualquier puntación otrogable por resolver satisfactoriamente casos de prueba.
A continuación se discrimina la puntuación para esta entrega:
- Implementación de requerimientos no funcionales: 15
- PR-B: 5 (1 segundo)
- PR-C: 10 (1 segundo)
- PR-D: 20 (2 segundos)
- PR-E: +20 (2 segundos)
PR-E corresponde a casos de prueba muy díficiles (en inglés evil) y su solución correcta en la arena otorga un bono de 20 puntos.
La sustentación es un factor entre 0 y 1 que pondera la puntuación enumerada anteriormente: entre mejor sea la sustentación, mayor será este factor.
Otros recursos