PROGRAMA DE CURSO Código Nombre CC5001 Taller de Implementación de Estructuras de Datos Nombre en Inglés Data Structures Implementation Workshop Unidades Horas de Horas Docencia Horas de Trabajo SCT Docentes Cátedra Auxiliar Personal 10 3 0 7 Requisitos Carácter del Curso AUTOR, CC30A Electivo Resultados de Aprendizaje Al finalizar el curso, el alumno será capaz de: 

Identificar rápidamente la técnica más adecuada para enfrentar un problema de programación nuevo.



Abordar problemas de programación de complejidad media, que requieran respuestas rápidas y precisas.



Implementar o utilizar estructuras de datos y algoritmos estudiados en cursos previos de computación



Entender las dificultades particulares de cada una de las estructuras de datos



Utilizar bibliotecas estándares de Java y C++ de estructuras de datos.

Metodología Docente Clases Expositivas, trabajo individual y en grupo.

Evaluación General La evaluación consiste de un proyecto individual y de actividades realizadas en equipo. Alguna de las tareas grupales serán realizadas en horario de cátedra de modo de poder guiar a los alumnos. Las evaluaciones individuales y grupales deben ser aprobadas independientemente. La evaluación individual consiste en la realización de 3 proyectos pequeños que combinen al menos 2 de las herramientas generales. Durante las actividades grupales se espera que los alumnos resuelvan al menos 40 problemas de la competencia ACM-ICPC. Las ponderaciones son 1/3 para la evaluación individual y 2/3 para la grupal.

Observación: Los grupos con mejor desempeño en las actividades grupales serán preseleccionados para participar en la competencia ACM-ICPC.

Unidades Temáticas Número 1

1. 2. 3. 4.

Nombre de la Unidad Duración en Semanas Estructuras de datos básicas 2 Resultados de Aprendizajes de la Referencias a Contenidos Unidad la Bibliografía Hashes Reconocer estructuras de datos [1], [7] Listas enlazadas abstractas básicas y sus Árboles binarios de búsqueda operaciones. Diccionarios

Número 2

Nombre de la Unidad Duración en Semanas Técnicas de Programación 2 Resultados de Aprendizajes de la Referencias a Contenidos Unidad la Bibliografía 1. Programación dinámica Conocer las principales estrategias [1], [2], [7] 2. Recursión de diseño de algoritmos. 3. Backtracking

Número 3

1. 2. 3. 4.

Nombre de la Unidad Duración en Semanas Herramientas Matemáticas 3 Resultados de Aprendizajes de la Referencias a Contenidos Unidad la Bibliografía Ecuaciones de recurrencia Reconocer las herramientas [1], [2], [3] Geometría euclideana matemáticas más utilizadas para la Combinatoria resolución de problemas de Teoría de números básica. programación. Resolver problemas Divisibilidad y congruencias. que requieran su comprensión. Algoritmo de Euclides.

Número 4

1. 2. 3. 4. 5.

Nombre de la Unidad Duración en Semanas Algoritmos en Lenguajes 2 Resultados de Aprendizajes de la Referencias a Contenidos Unidad la Bibliografía Hashes en Java Aprender a utilizar los objetos ya [1], [3], [8] Diccionarios en Java existentes en los lenguajes Java y Iteradores en Java C++ que representan las Listas y otros objetos en Java estructuras de datos básicas. Introducción a STL en C++

Número 5 Contenidos 1. Grafos:

Nombre de la Unidad Duración en Semanas Algoritmos Clásicos 4 Resultados de Aprendizajes de la Referencias a Unidad la Bibliografía Estudiar y utilizar algoritmos [1], [3], [8], [9]

1. Arboles generadores 2. Caminos mínimos 3. Cobertura 4. Flujos 2. Geometría: 1. Triangulaciones 2. Distancias y objetos algebráicos 3. Cobertura convexa

conocidos para la resolución de problemas de programación.

Bibliografía [1] S. S. Skiena, M. Revilla, "Programming Challenges". Springer, 2003. [2] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, “Introduction to Algorithms”, 2nd edition, MIT Press, 2001. [3] R. Sedgewick, "Algorithms in Java", 3rd edition. Addison-Wesley, 2003-2004. [4] Uva Online Judge: http://uva.onlinejudge.org/ [5] Project Euler: http://projecteuler.net/ [6] Google Code Jam: http://code.google.com/codejam/ [7] M. A. Weiss, "Data structures and problem solving using Java". Addison-Wesley, 1998. [8] B. Stroustrup, "The C++ Programming Language", 3rd edition. Addison-Wesley, 2004. [9] Joseph O'Rourke "Computational geometry in C", 2001.

Vigencia desde: Elaborado por:

Primavera 2009 Sebastián Kreft, Cristián Serpell