2014-1

Información general

Profesor Camilo Rocha (camilo.rocha *at* escuelaing.edu.co)

• Grupo 1: Lunes (D-211) 16:00 - 17:30, Martes (C1-204) 16:00 - 17:30, Martes (LAB) 17:30 - 19:00
• Grupo 2: Lunes (D-211) 16:00 - 17:30, Miércoles (C1-204) 10:00 - 11:30, Miércoles (LAB) 11:30 - 13:00

Horas de oficina Miércoles 14:30 - 17:30

Horario de atención de monitores

• Jueves (LAB) 13:00 - 14:30 (Monitor: Felipe Díaz)
• Lunes (LAB) 11:30 - 13:00 (Monitor: Carlos Angulo)

Programa del curso

Material

Ambientes virtuales

• DOMJudge
• Moodle
  • Grupo 1
  • Grupo 2

Colecciones en Python

• Listas y pilas
• Montones binarios y colas de prioridad
• Colas
• Complejidad temporal de algunas colecciones en Python

Conferencias y ejercicios resueltos

• Semana 1: Introducción al análisis y diseño de algoritmos
  • conferencia
• Semana 2: Análisis asintótico de funciones; el Teorema Maestro
  • Notación O (5 videos)
  • El Teorema Maestro (3 videos)
• Semana 3: Programación dinámica
  • Introducción (ver desde 13:43)
  • Knapsack
  • Rod cutting
  • Longest palindromic subsequence
• Semana 4: Idem
• Semana 5: Repaso y parcial tercio 1
• Semana 6: Estructuras de datos
  • introducción
  • montones binarios
    • introducción
    • operaciones
    • aplicación: colas de prioridad
    • aplicación: heapsort
• Semana 7: Listas
  • listas sencillamente encadenadas
  • listas doble y circularmente encadenadas
• Semana 8: Conjuntos, multiconjuntos y diccionarios (tablas de hashing)
  • conceptos básicos
  • funciones de hashing y compresión
• Semana 9: Conjuntos disyuntos; árboles, árboles binarios de búsqueda y árboles de búsqueda balanceados
  • conjuntos disyuntos
  • árboles y recorridos
  • árboles binarios de búsqueda (opcional)
  • árboles balanceados (opcional)
• Semana 10: Repaso y parcial tercio 2
• Semana 11: Grafos
  • representación
• Semana 12: Búsqueda en grafos
  • búsqueda en amplitud (BFS)
  • búsqueda en profundidad (DFS)
• Semana 13: Órden topológico y reintento
  • órden topológico
  • reintento (backtracking)
  • el problema de las N damas
• Semana 14: Árboles mínimos de cubrimiento (MST)
  • algoritmos voraces y el algoritmo de Prim
  • algoritmo de Kruskal
  • algoritmo de Prim
• Semana 15: Caminos más cortos (SSSP/ASSP)
  • Introducción SSSP/ASSP
  • algoritmo de Dijkstra (SSSP)
  • algoritmo de Bellman-Ford-Moore (SSSP)
  • algoritmo de Floyd-Warshall (SSSP)
• Semana 16: Flujo en redes
  • introducción y grafos residuales
  • algoritmo de Ford-Fulkerson

Maratón de Programación

• Categoría básica
  • enunciado
  • casos de prueba
  • clasificación final
• Categoría avanzada
  • enunciado
  • casos de prueba
  • clasificación final

Proyecto

The Hippie Puzzle: enunciado | arena | casos de prueba

• Documento de diseño (jueves 24 de abril).

Descripción de las estructuras de datos y algoritmos (alto nivel) para resolver el problema. Máximo dos páginas.

• Implementación y validación (lunes 5 miércoles 7 de mayo).

Sometimiento de la solución a DomJudge.

• Sustentación (viernes 9 16 de mayo).

Se sustenta la entrega del 5 7 de mayo y se modifica dicha solución para imprimir al menos una solución al rompecabezas si es que esta existe. Para esta entrega se liberarán casos de prueba adicionales y tiempos de ejecución.

Tareas

• Semanas 1 y 2 (para entregar 01/24 y 01/26)
  • enunciado
  • casos de prueba
  • plantillas
• Semanas 3 y 4 (para entregar 02/07 y 02/09)
  • enunciado
  • casos de prueba
• Semanas 6 y 7 (para entregar 02/28 y 03/02)
  • enunciado
  • casos de prueba
• Semanas 8 y 9 (para entregar 03/14 y 03/16)
  • enunciado
  • casos de prueba
• Semanas 11 y 12 (para entregar 04/04 y 04/06)
  • enunciado
  • casos de prueba
• Semanas 13 y 14 (para entregar 04/25 y 04/27)
  • enunciado
  • casos de prueba
• Semanas 15 y 16 (para entregar 05/09 y 05/11)
  • enunciado
  • casos de prueba

Otros recursos

• Parcial 1 (2013-2)
• Parcial 2 (2013-2)
• Examen Final (2013-2)
• Documentación de Python
• Terminal de Linux en línea