2019-2
Información general
Profesores
- Camilo Rocha (camilo.rocha *at* javerianacali.edu.co)
- Carlos Pinzón (carlos.pinzon *at* javerianacali.edu.co)
Horario
- Martes (Palmas - 3.1) 14:00 - 15:30
- Miércoles (Palmas - 3.2) 16:00 - 18:00
- Jueves (Palmas - 3.1) 14:00 - 15:30
Atención a estudiantes
- Lunes 10:00 - 12:00 (FIC 2-38)
- Martes 11:00 - 11:45 (FIC 2-38)
- Martes 16:00 - 17:00 (Guayacanes, 4to piso)
- Jueves 16:00 - 17:00 (Guayacanes, 4to piso)
Material
Examen final
- Fecha: noviembre 14 de 2019
- Horario: 14:00 - 16:00
- Salón: El Lago 2.4
Vínculos
- Arena de programación (tareas prácticas)
- Notas (actualizadas 11/19 -- incluye examen final)
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)
- Tarea 4: semanas 8 y 9 (para entregar 09/20 y 09/22)
- Tarea 5: semanas 11 y 12 (para entregar 10/24)
- enunciado (enunciado problema B corregido)
- casos de prueba (el problema C no se evaluará)
Sesiones
- Sesión 1 (07/23)
- Sesión 2 (07/24)
- Sesión 3 (07/25)
- Sesión 4 (07/30)
- Sesión 5 (07/31)
- Sesión 6 (08/01)
- Sesión 7 (08/06)
- Sesión 8 (08/07)
- festivo
- Sesión 9 (08/08)
- Búsqueda en profundidad (DFS)
- UVa 572 - Oil Deposits
- Sesión 10 (08/13)
- Búsqueda en amplitud (BFS)
- UVa 924 - Spreading the News
- Sesión 11 (08/14)
- Sesión 12 (08/15)
- Sesión 13 (08/20)
- Repaso
- Sesión 14 (08/21)
- Repaso
- Sesión 15 (08/22)
- Parcial 1
- Sesión 16 (08/27)
- Componentes fuertemente conexos
- El algoritmo de Gabow
- Sesión 17 (08/28)
- El algoritmo de Kosaraju (autor: Carlos Pinzón)
- Sesión 18 (08/29)
- El algoritmo de Tarjan para SCC (autor: Carlos Pinzón)
- Sesión 19 (09/03)
- Puntos de articulación y puentes
- Sesión 20 (09/04)
- Componentes bi-conectados (autor: Carlos Pinzón)
- Algoritmo de Tarjan para componentes bi-conectados (autor: Carlos Pinzón)
- Sesión 21 (09/05)
- DFS anotada y algunas propiedades
- Tablas de hash (material adicional)
- Sesión 22 (09/10)
- Árboles
- Conceptos básicos
- Representaciones
- Árboles
- Sesión 23 (09/11)
- Recorridos en árboles:
- preorden, inorder, posorder
- Propiedades de árboles:
- cantidad de nodos vs. cantidad de arcos
- un árbol es un grafo en el cual existe un único camino entre cualquier par de vértices
- Recorridos en árboles:
- Sesión 24 (09/12)
- Recorridos en árboles con diferentes representaciones
- Representación de árboles binarios con nodos
- clase bin_tree (autor: Francisco Suárez)
- Sesión 25 (09/17)
- Radio y diámetro
- excentricidad de un nodo
- radio de un grafo
- diámetro de un grafo
- cálculo del radio y diámetro de un grafo
- cálculo del radio y diámetro en un árbol
- Radio y diámetro
- Sesión 26 (09/18)
- Diámetro de un árbol (dividir y conquistar) y generación aleatoria de árboles
- código (autor: Carlos Pinzón)
- Diámetro de un árbol (dividir y conquistar) y generación aleatoria de árboles
- Sesión 27 (09/19)
- Códigos de Huffman (y clase node)
- Sesión 28 (09/24)
- Repaso
- Sesión 29 (09/25)
- Repaso
- Sesión 30 (10/01)
- Parcial 2
- Sesión 31 (10/02)
- ...
- Sesión 32 (10/03)
- SSSP y el Algoritmo de Dijkstra
- Sesión 33 (10/08)
- MST y el Algoritmo de Kruskal
- Union-find
- Sesión 34 (10/09)
- El algoritmo de Kruskal
- Sesión 35 (10/10)
- El algoritmo de Kruskal
- Sesión 36 (10/15)
- Árboles de segmentos
- Sesión 37 (10/16)
- Proyecto
- Sesión 38 (10/17)
- Árboles de segmentos
- Sesión 40 (10/22)
- String matching: Búsqueda de un patrón P en un texto T
- La noción de borde
- Sesión 41 (10/23)
- Arreglos de sufijos (i.e., Suffix Array)
- Sesión 42 (10/24)
- Sesión 43 (10/29)
- Sesión 44 (10/30)
- Repaso de probabilidad
- Sesión 45 (10/31)
- Sesión 46 (11/05)
- Sesión 47 (11/06)
- Sesión 48 (11/07)
- Cierre del curso
Exámenes pasados
- 2018-2: parcial 1, parcial 2, examen final
- 2019-1: parcial 1, parcial 2, examen final
Proyecto
Indexing App: enunciado | arena | casos de prueba
https://drive.google.com/file/d/1fdgDKHwX34Ky8ejf_3WYYDBiSQZ0nQh0/view?usp=sharing
Otros recursos