Tabla de Contenidos
Algoritmos y Estructuras de Datos II
- Docentes:
- Teóricos: Daniel Fridlender
- Prácticos: Juan Durán, Sergio Giro, Alejandro Tiraboschi.
- Taller: Damian Barsotti, Marcos Dione, Martín Domínguez.
- Ayudantes:
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
- Primeras dos clases y sus preguntas.
- Tercer y cuarta clases y sus preguntas.
- Quinta y sexta clases y sus preguntas.
- Recurrencias divide y vencerás (sexta clase) y sus preguntas.
- Recurrencias lineales homogéneas (séptima clase) y sus preguntas.
- Recurrencias no homogéneas (octava clase) y sus preguntas.
- Segunda parte
- Novena clase y sus preguntas.
- Tercera parte
- 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, Cálculo de Programas.
- Tutoriales de lenguaje C
- Otros
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.
- Algunos visualizadores
- Notación O
- Algunos visualizadores
- Árboles binarios
- Algunos visualizadores
Práctico
- Éste es el práctico correspondiente a toda la materia: 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
, funcionesstrerror
,perror
,err
,warn
,errx
,warnx
. Libreríaassert
.
- 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
- Proyecto 2: Cintas. Descargar cintas de lectura y escritura de tuplas en disco. Descargar diccionario de prueba. Descargar make file genérico (tiene además todos los parametros de deteccion de errores para el gcc).
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.