====== Algoritmos y Estructuras de Datos II ====== * Docentes: * Teóricos: Daniel Fridlender * Prácticos: Juan Durán, Sergio Giro, Alejandro Tiraboschi. * Taller: [[http://www.cs.famaf.unc.edu.ar/~damian|Damian Barsotti]], Marcos Dione, Martín Domínguez. * Ayudantes: FIXME ===== Generalidades ===== * Parciales: 3 (fechas preliminares: 16/4, 14/5 y 18/6). * Promoción: no hay. * Regularidad: estando inscripto como regular + aprobando 2 parciales + aprobando el taller. * Examen: examen escrito + resolución de problemas frente a la computadora (2 días). * Alumnos libres: ambas partes del examen contienen ejercicios adicionales. === Preguntas frecuentes === * Si apruebo los parciales pero no el taller, ¿deberé resolver ejercicios adicionales en el examen escrito? Sí, porque vas a rendir como alumno libre. * Si apruebo el taller pero no alcanzo a aprobar dos parciales, ¿deberé rendir un examen de laboratorio con ejercicios adicionales? Sí, porque vas a rendir como alumno libre. * El año pasado aprobé los parciales pero no el taller, ¿debo rendir los parciales nuevamente durante este año? Para poder regularizar, sí. * El año pasado aprobé el taller pero no alcancé a aprobar dos parciales, ¿debo volver a hacer el taller este año? Para poder regularizar, sí. * ¿Puedo rendir el examen final sin haber hecho el taller? Sí. Como alumno libre. * El año pasado regularicé (es decir, estaba inscripto como regular, aprobé los parciales y el taller). Quiero volver a cursar este año. ¿Voy a perder la regularidad obtenida el año pasado? Si te inscribís en la materia automáticamente perdés esa regularidad. Te conviene volver a cursarla sin inscribirte. ===== Teórico ===== ==== Bibliografía ==== * Notas de Algoritmos y Estructuras de Datos II. * Primera parte * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0801.pdf | Primeras dos clases}} y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0801.pdf | preguntas}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0802.pdf | Tercer y cuarta clases}} y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0802.pdf | preguntas}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0803.pdf | Quinta y sexta clases}} y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0803.pdf | preguntas}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0804.pdf | Recurrencias divide y vencerás}} (sexta clase) y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0804.pdf | preguntas}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0805.pdf | Recurrencias lineales homogéneas}} (séptima clase) y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0805.pdf | preguntas}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0806.pdf | Recurrencias no homogéneas}} (octava clase) y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0806.pdf | preguntas}}. * Segunda parte * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0807.pdf | Novena clase}} y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0807.pdf | preguntas}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0808.pdf | Décima y décimoprimera clases}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0809.pdf | Décimosegunda clase}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0810.pdf | Décimotercera, décimocuarta y décimoquinta clases}}. * Tercera parte * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0811.pdf | Decimosexta y decimoséptima (media) clases}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0812.pdf | Decimoséptima (media) y decimooctava clases}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0813.pdf | Decimonovena y vigésima clases}}. * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0814.pdf | Vigésimoprimera clase}}. * Brassard and Bratley, Fundamentals of Algoritmics. * Manber, Introduction to Algorithmics: A Creative Approach. * Bibliografía Complementaria * Cormen, Leiserson, Rivest y Stein, Introduction to Algorithms. * Balcázar, Programación Metódica. * Biggs, Matemática Discreta. * Kaldewaij, Programming: the Derivation of Algorithms. * Blanco, Smith y Barsotti, {{http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/apunte/main.pdf|Cálculo de Programas}}. * Tutoriales de lenguaje C * {{algo2:cursc.html | En castellano pero básico}} * [[http://www.cs.cf.ac.uk/Dave/C/ | En ingles pero muy completo]] * [[http://www.space.unibe.ch/comp_doc/c_manual/C/cref.html|Manual de referencia en inglés]] * Otros * {{algo2:main:cookoopvsadt90.pdf|Object-Oriented Programming Versus Abstract Data Types}} ==== Clases ==== * 01: (10/03/08 y 12/03/08) Presentación, motivación, ordenación por selección, conteo, ordenación por inserción. * 02: (17/03/08 y 19/03/08) Notación //O//, propiedades, regla del límite, jerarquía de funciones, notación complementaria. * 03: (26/03/08 y 31/03/08) Búsqueda lineal y binaria, ordenación por intercalación. * 04: (31/03/08) Recurrencias divide y vencerás. * 05: (07/04/08) Recurrencias lineales homogéneas. * 06: (09/04/08) Recurrencias no homogéneas. * 07: (14/04/08) Estructuras concretas/abstractas de datos. Estructuras concretas: arreglos, listas, tuplas, punteros. * 08: (21/04/08 y 23/04/08) Tipos abstractos de datos: pilas, colas y listas. Implementaciones de pilas y colas usando arreglos y listas. * 09: (28/04/08) Listas enlazadas, implementación de pilas y colas. * 10: (30/04/08, 05/05/08 y 07/05/08) Árboles binarios. Árboles binarios de búsqueda. TAD cola de prioridades. Heap. * 11: (12/05/08 y 26/05/08 (media)) Algoritmos divide y vencerás. * 12: (26/05/08 (media), 28/05/08 y 02/06/08) Algoritmos voraces. * 13: (04/06/08, 09/06/08 y 11/06/08) Programación dinámica. * 14: (18/06/08) Recorrida de grafos y backtracking. ==== Vínculos interesantes ==== * Algoritmos de ordenación. * {{http://en.wikipedia.org/wiki/Sorting_algorithms | en wikipedia}} * Algunos visualizadores * {{http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html}} * {{http://www.geocities.com/siliconvalley/network/1854/Sort1.html}} * {{http://math.hws.edu/TMCM/java/xSortLab/}} * {{http://www.ida.liu.se/~TDDB28/mtrl/demo/sorting/index.sv.shtml}} * {{http://thomas.baudel.name/Visualisation/VisuTri/}} * Notación //O// * {{http://en.wikipedia.org/wiki/O_notation | en wikipedia}} * Algunos visualizadores * {{http://www.math.com/students/graphing.html}} * {{http://www.coolmath.com/graphit/index.html}} * {{http://rechneronline.de/function-graphs/}} * Árboles binarios * Algunos visualizadores * {{http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm}} ===== Práctico ===== * Éste es el práctico correspondiente a toda la materia: {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/ejercicios2008.pdf | Práctico 2008}}. ===== Laboratorio ===== ==== Horarios ==== * Lunes 9 a 13 hs: Consultas y correciones de proyectos. * Viernes 14 a 16 hs: Teórico del laboratorio. * Viernes 16 a 18 hs: Consultas y práctica libre. Todas las clases son en el laboratorio de computación del 2do piso. ==== Clases ==== * 14/3: Revisión de distintas zonas de memoria al ejecutarse un programa. Memoria dinámica. Implementación de TAD's en memoria dinámica. Constructores, destructores y funciones que clonan. Ejemplo completo TAD Par usando la técnica. Lanzamiento proyecto 1. * 28/3: Implementación de listas con punteros. Implementacion de constructores y metodos sobre listas (tipo haskell). Problemas de memory leaks y punteros colgados en función tail. * 4/4: Cinta de elementos para manipular listas enlasadas (con inserción en posicion corriente y borrado del elemento corriente). Especificación abstracta con pre y post. Implementación con puntero a parte derecha (''c->pd''). Problema para insertar y borrar. Implementacion con nodo dummy dentro de la estructura (''c->cd''), puntero a uno antes de la parte derecha (''c->ppd''). * 11/4: Makefile exhaustivo. * 18/4: Manejo de errores. Errores de sintaxis, de lógica y de sistema. Variable ''errno'', funciones ''strerror'', ''perror'', ''err'', ''warn'', ''errx'', ''warnx''. Librería ''assert''. * 25/4: Implementaciones de mapas y conjuntos. Hash abierto. * 2/5: Implementación arboles binarios de buzqueda en C primera parte. Versiones recursivas e iterativas. Uso de pre y pos condiciones y versiones funcionales para diseñar y probar algorítmos. * 9/5: Implementación arboles binarios de buzqueda en C segunda parte. Desarrollo de función add iterativa usando anotaciones. * 16/5: Implementación de AVL. * 29/5: Kruskal con TAD's para proyecto. Abstracción de ''streams'' en C. ==== Proyectos ==== * {{algo2:main:2008:proy01.pdf|Proyecto 1: Diccionario sobre lista de asociaciones}}. * {{algo2:main:2008:proy02.pdf|Proyecto 2: Cintas}}. {{algo2:main:2008:libcrw.tgz|Descargar}} cintas de lectura y escritura de tuplas en disco. {{algo2:main:2008:diccionario.dic.gz|Descargar}} diccionario de prueba. {{algo2:main:2008:makefile_generico.gz|Descargar}} make file genérico (tiene además todos los parametros de deteccion de errores para el gcc). * {{algo2:main:2008:proy03.pdf|Proyecto 3: Hash}}. * {{algo2:main:2008:proy04.pdf|Proyecto 4: Abb}}. * {{algo2:main:2008:kruskal.pdf|Proyecto 5: Kruskal}}. ===== Instrucciones para inscribirse en la lista de mails ===== Enviar un mail a: minimalist@hal.famaf.unc.edu.ar con el subject: subscribe alualgo2 El cuerpo del mail se puede dejar en blanco. Despues de enviarlo debe llegar un mail donde diga que la subscripcion fue realizada correctamente. === !! Tener en cuenta !! === Si se cometio un error el sistema enviará un mail avisando. Por lo cual, siempre lea el mail de respuesta a la inscripción y verifique que no hubo un error. Si es así repita el proceso.