Algoritmos y Estructuras de Datos II

• Teóricos: Daniel Fridlender.
• Prácticos: Gonzalo Peralta y Alejandro Gadea (¡nuevo!).
• Laboratorio: Natalia Bidart, Matías Bordese, Diego Dubois, Leonardo Rodríguez y Araceli Acosta (¡nueva!).
  • Ayudantes: Daniel Bridera, Lucía Pappaterra y Milagro Teruel.

• Teóricos: lunes de 9 a 11hs y miércoles de 14 a 16hs, en el aula 17.
• Prácticos: lunes de 11 a 13hs y miércoles de 16 a 18hs, en el aula 17.
• Laboratorio: martes y jueves de 14 a 18hs. Los martes se dicta clase, se enuncian y evalúan los proyectos, y se atienden consultas. Los jueves solo se atienden consultas.

• Los contenidos se dividen en tres partes:
  • Análisis de algoritmos: algoritmos de ordenación, orden de un algoritmo, recurrencias.
  • Tipos abstractos de datos: tipos concretos versus tipos abstractos, contador, pila, cola, árboles.
  • Técnicas de programación: algoritmos voraces, divide y vencerás, programación dinámica, backtracking.
• Programa de la materia.

• Parciales: 2.
• Fechas preliminares: 23/4/14 y 18/6/14.
• Recuperatorio: 25/6/14. El recuperatorio no cuenta para la promoción.
• Proyectos del laboratorio: 4.
• Fechas preliminares de evaluación de proyectos: 25/3/14, 8 y 29/4/14, 13/5/14 y 10/6/14.
• Regularidad: aprobando dos parciales (eventualmente recuperando uno de ellos) + aprobando al menos 3 de los 4 proyectos del laboratorio (uno de ellos debe ser el 4to).
• Promoción: aprobando cada parcial con 6 o más, con promedio total de 7 o más + aprobando cada proyecto del laboratorio con 6 o más.
• Examen final: evaluación por escrito de teórico-práctico + resolución de problemas frente a la computadora (1 ó 2 días).
• Alumnos libres: ambas partes del examen (teórico y laboratorio) contienen ejercicios adicionales.
• Los alumnos que promocionan sólo los parciales o sólo los proyectos del laboratorio serán exceptuados de rendir la parte promocionada en las mesas de julio-agosto de 2014, únicamente.

• La regularidad requiere regularidad en el teórico/práctico y en el laboratorio?
  • Sí: la regularidad de la materia es un AND de la regularidad del teórico/práctico con la regularidad del taller.
• Si voy al laboratorio un jueves de 14 a 18hs, ¿tendré a quien consultar mis dudas?
  • Sí, habrá docentes o ayudantes a quienes podrás consultar.
• Si apruebo los parciales pero no los proyectos del laboratorio, ¿deberé resolver ejercicios adicionales en el examen escrito?
  • Sí, porque vas a rendir como alumno libre.
• Si apruebo los proyectos del laboratorio pero no alcanzo a aprobar los 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 los proyectos del laboratorio, ¿debo rendir los parciales nuevamente durante este año?
  • Para poder regularizar, sí.
• El año pasado aprobé los proyectos del laboratorio pero no alcancé a aprobar los parciales, ¿debo volver a hacer el laboratorio este año?
  • Para poder regularizar, sí.
• ¿Puedo rendir el examen final sin haber hecho el laboratorio?
  • Sí. Como alumno libre. Pero deberás demostrar suficientes conocimientos de programación durante el examen.
• El año pasado regularicé (es decir, estaba inscripto como regular, aprobé los parciales y los proyectos del laboratorio). 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.
• En ese caso, ¿qué pasa si este año promociono?
  • Te inscribís en la primera fecha de exámenes y te pasamos la nota de la promoción.
• Tengo condición de regular y promocioné los parciales pero no los proyectos del laboratorio. ¿Debo rendir el escrito también?
  • En las mesas de julio-agosto 2014, no. Después de esas mesas, sí.
• Tengo condición de regular y promocioné los proyectos del laboratorio pero no los parciales. ¿Debo rendir el laboratorio también?
  • En las mesas de julio-agosto 2014, no. Después de esas mesas, sí.

• Primer parcial, 23/04/2014.
• Segundo parcial, 18/06/2014.
• Primer y segundo recuperatorios, 25/06/2014.

Lunes de 9 a 11hs y miércoles de 14 a 16hs, en el aula 17.

• Notas de Algoritmos y Estructuras de Datos II.
  • 01.analisis.pdf
  • 02.tiposconcretos.pdf
  • 03.tiposabstractos.pdf
  • 04.implementacioneselementales.pdf
  • 05.listasenlazadas.pdf
  • 06.arbolesbinarios.pdf
  • 07.tecnicasavanzadas.pdf
  • 08.dfs.pdf

• 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
  • En castellano pero básico
  • En ingles pero muy completo
  • Manual de referencia en inglés
    This is a reference manual for the C programming language as implemented by the GNU Compiler Collection (GCC).

• Otros
  • Object-Oriented Programming Versus Abstract Data Types

• Primera parte: Análisis de Algoritmos.
  • 10/03/14: Introducción a la materia, análisis de algoritmos (motivación), problema del bibliotecario, ordenación por selección, número de comparaciones, conteo de operaciones, número de intercambios. 01.ordenacion_seleccion.pdf
  • 12/03/14: Repaso. Ordenación por inserción, análisis, mejor caso, peor caso y caso medio. 01b.ordenacion_insercion.pdf. Ordenación por intercalación. 02.ordenacion_intercalacion_filminas.pdf
  • 17/03/14: Análisis de la ordenación por intercalación. Ordenación rápida. 03.ordenacion_rapida_filminas.pdf. Ordenación en el sitio www.sorting-algorithms.com.
  • 19/03/14: Notación O, Omega y Theta. Propiedades elementales. Regla del límite. Jerarquía. Propiedades adicionales. 04.notacion_o.pdf
  • 24/03/14: Feriado.
  • 26/03/14: Notación O, Omega y Theta. Propiedades. Jerarquía. Algoritmos divide y vencerás. Recurrencias divide y vencerás. 05.recurrencias_dyv.pdf
  • 31/03/14: Recurrencias homogéneas y no homogéneas. 06.recurrencias_homogeneas_y_no.pdf
• Segunda parte: Estructuras de Datos.
  • 07/04/14: Tipos de datos. Tipos concretos y tipos abstractos. Tipos concretos: arreglos, listas, tuplas y punteros.07_tipos.pdf
  • 09/04/14: Tipos abstractos de datos. Paréntesis balanceados, TAD contador (grabá en tu disco y borrá la extensión .pdf). Delimitadores balanceados, TAD pila (grabá en tu disco y borrá la extensión .pdf). 08.tads.pdf
  • 14/04/14: Implementación del TAD contador. Listas enlazadas. Implementación del TAD pila usando listas enlazadas. 11.listas_enlazadas.pdf
  • 16/04/14: Tipos abstractos de datos. Productor-consumidor. Buffer. TAD cola. 09.tads.pdf
  • 21/04/14: Tipos abstractos de datos. Implementaciones elementales (basadas en arreglos) de pila y cola. 10.implementaciones_elementales.pdf
  • 23/04/14: Primer parcial.
  • 28/04/14: Resolución del parcial. Árboles binarios y árboles binarios de búsqueda.
  • 30/04/14: Árboles binarios de búsqueda y heaps. 14.heap.pdf
  • 05/05/14: Implementación de heap, cola de prioridades, heapsort. 14.heap.pdf
• Tercera parte: Algoritmos Avanzados.
  • 07/05/14: Algoritmos voraces. Forma general. Problema de la moneda. Problema de la mochila. 15.voraz.pdf
  • 12/05/14: Algoritmos voraces. Problema del árbol generador de costo mínimo. Algoritmo de Prim. Algoritmo de Kruskal. Problema Union-Find. 16.voraz.pdf
  • 14/05/14: Algoritmos voraces. Problema del camino de costo mínimo. Algoritmo de Dijkstra. 17.dijkstra.pdf
  • 19/05/14: Backtracking. Problema de la moneda. Casos sin solución voraz. Solución que usa backtracking. Generalización. Recursión. Exploración de todas las posibilidades. 18.backtracking.pdf
  • 21/05/14: Paro (no hay teórico pero sí práctico). Leer por su propia cuenta el apunte y las filminas. Programación Dinámica. Problema de la moneda. Problema de la mochila. 19.programacion_dinamica.pdf
  • 26/05/14: Programación dinámica. Algoritmo de Floyd para el camino de costo mínimo entre todo par de vértices. 20.programacion_dinamica.pdf
  • 28/05/14: Algoritmo de Floyd, cálculo de los caminos. Obtención de las soluciones en los problemas de la moneda y la mochila.
  • 02/06/14: Recorrida de grafos. 21.dfs.pdf
  • 04/06/14: Backtracking es DFS en un grafo implícito. El problema de n reinas, (n reinas en Haskell). 22.8reinas.pdf
  • 09/06/14: Repaso de algoritmos voraces 23.combustible.pdf.
  • 11/06/14: Repaso de backtracking (8 reinas en c).
  • 16/06/14: Repaso de backtracking y programación dinámica.

• Algoritmos de ordenación.
  • en wikipedia
  • Algunos visualizadores
    • http://www.sorting-algorithms.com/
    • http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html
    • http://math.hws.edu/TMCM/java/xSortLab/
    • http://thomas.baudel.name/Visualisation/VisuTri/
  • Algo-Ritmos
    • Ordenación por intercalación
    • Ordenación rápida
• Notación O
  • en wikipedia
  • Visualizador
    • function-graphs
• TADs
  • Algunos visualizadores
    • Pilas y colas download.html
    • Árboles binarios AVL

Lunes de 11 a 13hs y miércoles de 16 a 18hs, en el aula 17.

• Práctico 1: Análisis de algoritmos Parte 1 y Parte 2
• Práctico 2: Estructuras de datos practico2.pdf
• Práctico 3: Tipos abstractos de datos - Árboles Práctico 3
• Práctico 4: Algoritmos voraces. Práctico 4
• Práctico 5: Backtracking, programación dinámica y recorrido de grafos. Práctico 5

Los grupos serán de 2 (dos) personas. Mínimo 2, máximo 2. O sea, 2 .

• Martes 14 a 18 hs: Teóricos del taller, presentación de enunciados, entregas y evaluación de proyectos, consultas.
• Jueves 14 a 18 hs: Uso del laboratorio y consultas.

Todas las clases son en el laboratorio de computación del 2do piso (aula 28).

Intro a punteros - slides

Punteros - slides

Intro a TADs

GDB - slides

Makefile - slides

• Proyecto 1: Algoritmos de Ordenación
  • Enunciado
  • Esqueleto de código
• Proyecto 2: Tipos Abstractos de Datos, Diccionarios y Listas enlazadas
  • Enunciado parte A, implementación del TAD dict y main.c
  • Enunciado parte B, implementación de los TAD list y pair
  • Esqueleto de código para x86_64/amd64 (NUEVO!!! subido el 2014-04-14)
  • Esqueleto de código para i386 (NUEVO!!! subido el 2014-04-14)
• Proyecto 3: Tipos Abstractos de Datos, Árboles Binarios de Búsqueda
  • Enunciado (no hay esqueleto para este proyecto)
• Proyecto 4: Kruskal, el algoritmos para generar grafos de costo mínimo
  • Enunciado
  • Esqueleto de código para i386 y x86_64 (los .o para cada arquitectura están adentro de carpetas i386/ y x86_64/)

Cómo correr los tests de unidad de los proyectos: ver detalle en este tutorial.

A lo largo de este cuatrimestre, las entregas de los proyectos y las entregas de los “parcialitos” van a ser a través de nuestro ayudante, Jaime.

Jaime es un ejecutor de tareas muy muy simple. Por cada proyecto, Jaime va a tener disponible un listado de tareas que va a permitir correr una serie de tests sobre el código producido por cada alumno.

Para visitar Jaime, ir a http://jaime.no-ip.info/. Es obligatorio tener un usuario, y se va a crear automáticamente un usuario por cada miembro de cada grupo del taller. Por cualquier duda, consultar en la lista de la materia.

Tenemos un googlegroup para los alumnos y los docentes en la siguiente dirección:

https://groups.google.com/d/forum/famaf-ayed2

Para subscribirse, visitar el siguiente link:

http://groups.google.com/group/famaf-ayed2/subscribe

Por favor elegir una dirección de mail que lean todos los días y que no tenga restricciones de tamaño. No es obligatorio que sea un email de gmail. Las direcciones de hotmail/outlook están particularmente no recomendadas ya que suelen llenarse rápido y no les llegan los correos.

IMPORTANTE 1: una vez que se subscribieron al grupo, ir a la casilla de mail que usaron y aceptar la invitación.

IMPORTANTE 2: si ya estaban logueados en gmail, les aparece un diálogo para la subscripción donde tienen que elegir, entre otras cosas, el tipo de envíos de los emails: elegir “todos los emails”, como se muestra acá:

Para mandar un mail a la lista de la materia, escribir a:

famaf-ayed2@googlegroups.com