Información general
Profesores
- Camilo Rocha (camilo.rocha *at* javerianacali.edu.co)
- Carlos Pinzón (carlos.pinzon *at* javerianacali.edu.co)
Horario
- Martes (Palmas - 2.4) 14:00 - 15:30
- Miércoles (Palmas - 3.2) 16:00 - 17:30
- Jueves (Palmas - 2.4) 14:00 - 15:30
Atención a estudiantes
- Martes 11:00 - 12:00 (Oficina 2-38, Facultad de Ingeniería)
- Jueves 10:00 - 11:00 (Laboratorio DECC - Guayacanes 4o piso)
- Jueves 11:00 - 12:00 (Oficina 2-38, Facultad de Ingeniería)
- Viernes 10:00 - 11:00 (Laboratorio DECC - Guayacanes 4o piso)
Programa del curso
Material
Vínculos
Tareas
- Tarea 1: semanas 1 y 2 (para entregar 08/03 y 08/05)
- Tarea 2: semanas 3 y 4 (para entregar 08/17 y 08/19)
- Tarea 3: semanas 6 y 7 (para entregar 09/07 y 09/09)
- Tarea 4: semanas 8 y 9 (para entregar 09/21 y 09/23)
- Tarea 5: semanas 11 y 12 (para entregar 10/17)
- Tarea 6: semanas 13, 14 y 15 (para entregar 11/04)
Sesiones
- Sesión 1 (07/24)
- Sesión 2 (07/25)
- Sesión 3 (07/26)
- Sesión 4 (07/31)
- Sesión 5 (08/01)
- Sesión 6 (08/02)
- Sesión 7 (08/07)
- Sesión 8 (08/08)
- Sesión 9 (08/09)
- Sesión 10 (08/14)
- Sesión 11 (08/15)
- Sesión 12 (08/16)
- Sesión 13 (08/21)
- Ejercicios de DFS y BFS
- Repaso
- Sesión 14 (08/22)
- Sesión 15 (08/23)
- Sesión 16 (08/28)
- Sesión 17 (08/29)
- Sesión 18 (08/30)
- Sesión 19 (09/04)
- Puntos de articulación y puentes
- Sesión 20 (09/05)
- Sesión 21 (09/06)
- Sesión 22 (09/11)
- Sesión 23 (09/12)
- Sesión 24 (09/13):
- Sesión 25 (09/18)
- Sesión 26 (09/19)
- Sesión 27 (09/20)
- Sesión 28 (09/25)
- Sesión 29 (09/26)
- Sesión 30 (09/27):
- Sesión 31 (10/02)
- Sesión 32 (10/03)
- Sesión 33 (10/04)
- El problema SSSP y el algoritmo de Dijkstra
- Sesión 34 (10/09)
- Repaso del algoritmo de Dijkstra
- Sesión 35 (10/10)
- Sesión 36 (10/11)
- Conjuntos disyuntos
- El problema MST y el algoritmo de Kruskal
- Sesión 37 (10/16)
- Explicación ejercicios tarea 5
- Explicación del proyecto
- Sesión 38 (10/17)
- Sesión 39 (10/18)
- Sesión 40 (10/23)
- Sesión 41 (10/24)
- Sesión 42 (10/25)
- Sesión 43 (10/30)
- Árreglos de sufijos y LCP
- Sesión 44 (10/31)
- Árreglos de sufijos y LCP
- Sesión 45 (11/01)
- Pattern matching con Knuth-Bendix-Pratt
- Sesión 46 (11/06)
- Sesión 47 (11/07)
- Sesión 48 (11/08)
Proyecto
El objetivo principal del proyecto es emplear algorítmos, técnicas y estructuras de datos estudiados en el curso para analizar la interacción de usuarios en redes sociales. Se utilizarán datos obtenidos de la página Reddit correspondientes a foros de discusión disponibles públicamente.
El proyecto puede ser desarrollado en grupos de máximo dos personas, y consta de tres entregas y una sustentación. Las fechas de las entregas y de la sustentación se establecen a continuación:
- Entrega 0: octubre 24 de 2018
- Entrega 1:
octubre 31 de 2018 noviembre 18 de 2018 Entrega 2: noviembre 8 de 2018- Sustentación:
noviembre 9 de 2018 noviembre 19 de 2018
Entrega 0: casos de prueba
El objetivo de esta entrega es desarrollar un algoritmo que, dada la representación de uno o más foros de discusión, produce una representación computacional de la estructura de los foros a modo de árbol. Además, los nodos del árbol deben consolidar cierta información del foro de discusión.
- Cada archivo de entrada consta de una secuencia de líneas de texto con la siguiente estructura:
{indent_arrow}{body}[{author}|{ups}|{downs}|{comment_id}|{date}]
en donde
- indent_arrow puede ser >, -->, ---->, ..., según la profundidad del comentario, es decir, > corresponde al post principal, --> a comentarios del post, ---> a comentarios de comentarios, etc
- body es el texto del comentario y no contiene saltos de línea
- author es el username del autor del comentario
- ups y downs son la cantidad de votos a favor y en contra del comentario, respectivamente
- comment_id es un identificador del comentario
- date es la fecha en que se publicó el comentario
- Para cada caso (entrada con la estructura anterior) se deben generar:
- el recorrido en preorden del árbol asociado a la discusión, empleando tantas líneas como árboles aparezcan en la entrada y separando cada par de identificadores consecutivos por un espacio en blanco
- para cada post la cantidad de votos positivos y negativos correspondientes al sub-árbol del cual es raíz, siguiendo el orden correspondiente al establecido en el numeral anterior. La cantidad de votos es separada por un espacio para cada nodo y se imprime una linea por nodo
- la lista de usuarios (en orden descendente por la cantidad de comentarios y desempatada por orden lexicográfico, cuando sea necesario), uno por línea, con la cantidad de comentarios hechos, separando estas dos expresiones con un espacio en blanco.
Entrega 1: bajar enunciado (linux, windows)
Otros recursos