Algoritmos y Estructuras de Datos II

• Teóricos: Daniel Fridlender.
• Prácticos: Silvia Pelozo.
  • Ayudantes: Felipe Espósito, Emmanuel Gunther.
• Laboratorio: Natalia Bidart, Matías Bordese, Diego Dubois y Leonardo Rodríguez.
  • Ayudantes: David Arch, Maximiliano Bustos y Leandro Ramos.

• 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, enuncian los proyectos y atienden consultas. Los jueves también se atienden consultas.

• Parciales: 3.
• Fechas preliminares: 16/4/2012, 14/5/2012 y 21/6/2012.
• Recuperatorio: el jueves 7/6/2012 de 14 a 18hs quienes no hayan aprobado el primer o segundo parcial tendrán la opción de recuperar. Quienes no hayan aprobado ninguno de los dos deberán elegir cuál recuperan. El recuperatorio no cuenta para la promoción.
• Proyectos del laboratorio: 4.
• Promoción: aprobando cada parcial con 6 o más, con promedio de 7 o más, y aprobando cada proyecto del laboratorio con 7 o más.
• Regularidad: aprobando dos parciales + aprobando cada proyecto del laboratorio (con 4 o más).
• Examen: examen escrito + resolución de problemas frente a la computadora (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 2012.

• 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é rendir un examen de laboratorio con ejercicios adicionales?
  • Sí, porque vas a rendir como alumno libre.
• Si apruebo los proyectos del laboratorio pero no alcanzo a aprobar los parciales, ¿deberé resolver ejercicios adicionales en el examen escrito?
  • 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.
• Saqué 7 o más en los tres parciales pero no en los proyectos del laboratorio. ¿Debo rendir el escrito también?
  • En las mesas de julio-agosto 2012, no. Después de esas mesas, sí.
• Saqué 7 o más en los proyectos del laboratorio pero no en los parciales. ¿Debo rendir el laboratorio también?
  • En las mesas de julio-agosto 2012, no. Después de esas mesas, sí.

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

• Notas de Algoritmos y Estructuras de Datos II.
  • Primera parte: Análisis de Algoritmos.
  • Segunda parte: Estructuras de Datos.
    • Tipos concretos.
    • Tipos abstractos de datos. TADs Contador, Pila y Cola en Haskell.
    • Implementaciones elementales.
    • Listas enlazadas con su addenda.
    • Árboles binarios.
  • Tercera parte: Algoritmos Avanzados, Recorrida de grafos.
• 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.
  • Lunes 12 de marzo: presentación de la materia, introducción, distinción entre qué hace un algoritmo y cómo lo hace. Motivación: problema del bibliotecario. Ordenación por selección. Demos visuales. Procedimiento selection_sort en pseudo-código. Diseño top-down, procedimiento swap, función min_pos_from. Beneficio de usar swap. Análisis del algoritmo, elección de operación elemental, conteo. Aplicación al problema del bibliotecario. Método de conteo de operaciones de un algoritmo.
  • Miércoles 14 de marzo: Repaso. Conteo mecánico de comparaciones del selection_sort. Procedimiento insertion_sort en pseudo-código. Procedimiento insert. Análisis del algoritmo. Peor y mejor caso. Caso medio. Demos visuales.
  • Lunes 19 de marzo: Repaso, número de comparaciones de la ordenación por selección y por inserción. Notación O, Omega y Theta. Propiedades elementales. Equivalencias. Regla del límite, enunciado y demostración.
  • Miércoles 21 de marzo: Repaso, regla del límite. Jerarquía de funciones según su orden de crecimiento. Terminología.
  • Lunes 26 de marzo: Problema del bibliotecario. Ordenación por intercalación. Ordenación rápida.
  • Miércoles 28 de marzo: Orden de la ordenación por intercalación. Recurrencias divide y vencerás. Búsqueda lineal y búsqueda binaria.
  • Lunes 2 de abril: Feriado.
  • Miércoles 4 de abril: Recurrencias homogéneas y no homogéneas.
  • Lunes 9 de abril: Repaso de análisis y recurrencias.
• Segunda parte: Estructuras de Datos.
  • Miércoles 11 de abril: Tipos de datos. Tipos concretos.
  • Lunes 16 de abril: Primer parcial.
  • Miércoles 18 de abril: Tipos abstractos. Paréntesis balanceados, TAD contador. Paréntesis, corchetes, llaves, etc, TAD pila.
  • Lunes 23 de abril: Implementaciones del TAD pila: listas, listas enlazadas, arreglos. Eficiencia.
  • Miércoles 25 de abril: TAD cola, especificación e implementación.
  • Lunes 30 de abril: Feriado
  • Miércoles 2 de mayo: Implementación de colas con listas enlazadas, listas circulares, arreglos circulares.
  • Lunes 7 de mayo: Cola de prioridades. Implementación con listas enlazadas circulares. Árboles binarios. Implementación con punteros.
  • Miércoles 9 de mayo: Árboles binarios de búsqueda y heaps.
  • Lunes 14 de mayo: Segundo parcial.
• Tercera parte: Algoritmos Avanzados.
  • Miércoles 16 de mayo: Implementación de cola de prioridades usando heaps. Heapsort. Algoritmos voraces. Algoritmo de Kruskal.
  • Lunes 28 de mayo: Problema union-find. Algoritmo de Prim. Forma general de los algoritmos voraces.
  • Miércoles 30 de mayo: Algoritmo de Dijkstra. Problema de la moneda. Problema de la mochila.
  • Lunes 4 de junio: Divide y vencerás (ya vimos). Backtracking. Problema de la moneda. Problema de la mochila. Problema de los caminos mńimos.
  • Miércoles 6 de junio: Programación dinámica. Fibonacci. Problema de la moneda. Problema de la mochila. Algoritmo de Floyd.
  • Lunes 11 de junio: Recorrida de árboles y grafos. DFS.
  • Miércoles 13 de junio: DFS, BFS y últimas palabras sobre backtracking.

• Algoritmos de ordenación.
  • en wikipedia
  • Algunos visualizadores
    • sorting-demo.html
    • xSortLab
    • VisuTri
• 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

Práctico 1 (segunda parte)

Práctico 2 (primera parte)

Práctico 2 (segunda parte)

Práctico 3

En Guarani (hasta primer segundo parcial recuperatorio).

Los grupos serán de 2 (dos) personas. Mínimo 2, máximo 2. O sea, 2 . El listado completo de grupos y mapeo a profes encargados es: grupos del lab.

• Martes 14 a 18 hs: Teórico del taller y 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).

• Teórico de TADs, punteros y manejo de memoria en C
• Filminas de la charla de make
• Filminas GDB

• Proyecto 1: Ordenación, algoritmos elementales.
  • Enunciado del proyecto 1
  • Esqueleto del código a completar (versión nueva 0.99.1)
• Proyecto 1.b: Ordenación, algoritmos avanzados.
  • Enunciado del proyecto 1.b
  • Archivos de entrada para realizar la tabla comparativa
• Proyecto 2: Tipos Abstractos de Datos.
  • Enunciado del proyecto 2
  • Esqueleto del código a extender (para arquitecturas de 64 bits)
  • Esqueleto del código a extender (para arquitecturas de 32 bits)
  • Esqueleto del código a extender (para Mac)
• Proyecto 2b: Listas Enlazadas.
  • Enunciado del proyecto 2.b
• Proyecto 3: Árboles Binarios de Búsqueda.
  • Enunciado del proyecto 3
• Proyecto 4: Algoritmo de Kruskal.
  • Enunciado del proyecto 4 (Versión actualizada al 5 de Junio de 2012)
  • Esqueleto del código a extender (para todas las arquitecturas, incluye los .h del enunciado)

Desde el webmail del FaMAF enviar un mail a:

alualgo2-join@famaf.unc.edu.ar

con cualquier subject o cuerpo del mail.

Después de enviarlo debe llegar un mail con un link a una página donde donde se deben llenar los datos personales.

Todo esto hay que hacerlo desde el webmail del FaMAF.

Desde el webmail del FaMAF enviar un mail a:

alualgo2@famaf.unc.edu.ar

Tener en cuenta que todos los alumnos y todos los profes reciben los mails de esta lista.

Si se cometió 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.

Cualquier problema consultar con los administradores del laboratorio.