2017-1
Información general
Profesor Camilo Rocha (camilo.rocha *at* javerianacali.edu.co)
- Martes (Palmas-2.4) 09:00 - 11:00
- Jueves (Palmas-2.4) 09:00 - 11:00
Horas de oficina Oficina 2-38, Facultad de Ingeniería
- Martes 11:00 - 12:00
- Miércoles 11:00 - 12:00
- Jueves 16:00 - 17:00
Horario de atención de monitores No habrá.
Material
Vínculos
- Arena de programación (tareas prácticas)
- Arena de programación (proyecto)
- Notas (actualizado 06/06)
Tareas
- Tarea 1: sesiones 1-4 (para entregar 02/03 y 02/05)
- Tarea 2: sesiones 5-8 (para entergar 02/17 y 02/19)
- Tarea 3: sesiones 13-14 (para entregar 03/16)
- Tarea 4: sesiones 15-18 (para entregar 04/04)
- enunciado (el problema D ha sido eliminado)
- casos de prueba
- Tarea 5: sesiones 20-32 (para entregar 06/01)
Sesiones
- Sesión 1 (01/24)
- Sesión 2 (01/26)
- Sesión 3 (01/31)
- Sesión 4 (02/02)
- Sesión 5 (02/07)
- Sesión 6 (02/09)
- Sesión 7 (02/14)
- Sesión 8 (02/16)
- Sesión 9 (02/21)
- Sesión 10 (02/23)
- Sesión 11 (02/28)
- Sesión 12 (03/02)
- Solución Parcial 1
- Asignación exposiciones
- Sesión 13 (03/07)
- Listas
- Listas doblemente encadenadas con centinela (clase clist)
- Pilas
- Notas de clase
- Pilas con 'shallow embedding' (clase stack)
- Pilas con 'deep embedding' usando la clase clist (clase stack)
- Diccionarios (material por Juan Diego Patiño)
- Exposición
- Hashtables (clase HashTable)
- Listas
- Sesión 14 (03/09)
- Montones binarios minimales
- Notas de clase
- Montones binarios minimales con arreglos (clase minheap)
- Colas de prioridad con modificación eficiente de prioridades (clase pqueue)
- Montones binarios minimales
- Sesión 15 (03/14)
- Sesión 16 (03/16)
- Sesión 17 (03/21)
- Árboles de sufijos
- Sesión 18 (03/23)
- El algoritmo de Knuth-Morris-Pratt
- Sesión 19 (03/28)
- Sesión 20 (03/30)
- Sesión 21 (04/04)
- Sesión 22 (04/06)
- DISCO
- Sesión 23 (04/18)
- Parcial 2
- Sesión 24 (04/20)
- Solución parcial 2
- Sesión 25 (04/25)
- Introducción a teoría de la complejidad
- Sesión 26 (04/27)
- Salida de campo
- Sesión 27 (05/02)
- Sesión 28 (05/04)
- Sesión 29 (05/09)
- Vertex-Cover es NP-Completo
- Sesión 30 (05/11)
- TSP es NP-Completo
- Algoritmo de aproximación para Vertex-Cover
- Algoritmo de aproximación para TSP
Exámenes pasados
- 2016-1: parcial 1, parcial 2, examen final
- 2016-2: parcial 1, parcial 2, examen final
Proyecto
Chinese Ink: enunciado | arena | casos de prueba (FP-C)
- Entrega 0 (10%): viernes 6 de abril (4pm en el Departamento)
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%): viernes 28 de abril (11:59pm en la arena)
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.
- Contar con 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.
- Entrega 2 (60%):
viernes 12sábado 13 de mayo (11:59pm en la arena) yviernes 19lunes 15 de mayo (sustentación)
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 (FP-B), medios (FP-C) y difíciles (FP-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 FP-B, FP-C y FP-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á máximo 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: 10
- FP-B: 5 (3 segundos)
- FP-C: 10 (3 segundos)
- FP-D: 15 (2 segundoss)
- FP-E: +20 (2 segundos)
- Sustentación: 20
FP-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.
Otros recursos