Algoritmos y Estructuras de Datos II

• Teóricos: Daniel Fridlender.
• Prácticos: Silvia Pelozo y Alejandro Tiraboschi.
  • Ayudantes: Martín Becerra.
• Laboratorio: Natalia Bidart, Matías Bordese, Diego Dubois y Leonardo Rodríguez.
  • Ayudantes: Maximiliano Bustos, Luciano Silvi 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 también 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: 29/4/13 y 17/6/13.
• Recuperatorio: 24/6/13. El recuperatorio no cuenta para la promoción.
• Proyectos del laboratorio: 4.
• Fechas preliminares de evaluación de proyectos: 9/4/13, 7/5/13, 28/5/13 y 18/6/13.
• 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 2013, ú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 2013, 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 2013, no. Después de esas mesas, sí.

• Primer parcial, 29/04/2013.
• Segundo parcial, 17/06/2013.
• Primer recuperatorio, 24/06/2013.
• Segundo recuperatorio, 24/06/2013.

• Primer final, 03/07/2013.
• Segundo final, 24/07/2013.

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.
  • 11/03/13: 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, ordenación por inserción, análisis, mejor caso, peor caso y caso medio. 01.ordenacion_elemental_filminas.pdf. Ordenación por selección y por inserción en el sitio www.sorting-algorithms.com.
  • 13/03/13: Repaso. Análisis de algoritmos. Ordenación por intercalación. 02.ordenacion_intercalacion_filminas.pdf.
  • 18/03/13: Análisis de la ordenación por intercalación. Ordenación rápida.03.ordenacion_rapida_filminas.pdf.
  • 20/03/13: Notación O, Omega y Theta. Propiedades elementales. Regla del límite. Jerarquía. Propiedades adicionales. 04.notacion_o.pdf.
  • 25/03/13: Notación O, Omega y Theta. Propiedades. Jerarquía. Algoritmos divide y vencerás. Recurrencias divide y vencerás.05.recurrencias_dyv.pdf
  • 27/03/13: Recurrencias homogéneas y no homogéneas.06.recurrencias_homogeneas_y_no.pdf
• Segunda parte: Estructuras de Datos.
  • 03/04/13: Tipos de datos. Tipos concretos y tipos abstractos. Tipos concretos: arreglos, listas, tuplas y punteros.07_tipos.pdf
  • 08/04/13: Tipos abstractos de datos. Paréntesis balanceados, TAD contador. Delimitadores balanceados, TAD pila.08.tads.pdf
  • 10/04/13: Tipos abstractos de datos. Productor-consumidor. Buffer. TAD cola. TAD cola de prioridades. 09.tads.pdf
  • 15/04/13: Implementaciones elementales. Implementaciones de los TAD contador, pila y cola usando enteros, listas y arreglos. 10.implementaciones_elementales.pdf. Pilas y colas en arreglos y demo de factorial en el sitio http://www.cs.usfca.edu/~galles/visualization/Algorithms.html
  • 17/04/13: Implementaciones avanzadas: listas enlazadas. Implementaciones de pilas y colas usando listas enlazadas.11.listas_enlazadas.pdf
  • 22/04/13: Árboles binarios. Introducción, terminología. Especificación, implementación. Posición. Repaso para el parcial. 12.arboles_binarios.pdf
  • 24/04/13: Repaso. 13.repaso.pdf
  • 29/04/13: 1er parcial.
  • 06/05/13: Resolución del primer parcial. Repaso de árboles binarios. Árboles binarios de búsqueda (ABBs). Ejemplos. Definición. TAD diccionario: especificación e implementación utilizando ABBS. 14.abb.pdf
  • 08/05/13: Comentarios sobre errores frecuentes del parcial. Heaps. Ejemplos. Definición. Inserción en un heap. Flotar un elemento. Borrado en un heap. Hundir un elemento. Implementación de un heap en un arreglo. Implementación de cola de prioridades usando heaps. Heapsort. 15.heap.pdf
• Tercera parte: Algoritmos Avanzados.
  • 13/05/13: Algoritmos voraces, forma general, problema de la moneda, problema de la mochila. Árboles generadores de costo mínimo. Algoritmo de Prim. 16.voraz.pdf
  • 15/05/13: Algoritmo de Kruskal. Problema union-find. 17.voraz.pdf
  • 20/05/13: Problema del camino de costo mínimo. Algoritmo de Dijkstra. 18.dijkstra.pdf
  • 22/05/13: Repaso de algoritmos voraces. Problema de las ballenas (tomado del práctico).
  • 27/05/13: Backtracking: problema de la moneda, problema de la mochila. Problema del camino de costo mínimo entre todo par de vértices de un grafo dirigido.19.backtracking.pdf
  • 29/05/13: Programación dinámica. Problema de la moneda. Problema de la mochila. 20.programacion_dinamica.pdf
  • 03/06/13: Programación dinámica. Algoritmo de Floyd. Recuperación de la solución óptima en el problema de la moneda, de la mochila y algoritmo de Floyd.21.programacion_dinamica.pdf
  • 05/06/13: Recorrida de grafos: árboles binarios, árboles finitarios, grafos en general. DFS y BFS.22.dfs.pdf
  • 10/06/13: Repaso: backtracking y dfs, 8 reinas.23.8reinas.pdf Además, un programita en Haskell que genera todas las soluciones al problema de n reinas. Para usarlo, cambiale la extensión por .hs
  • 12/06/13: Repaso: algoritmos voraces. 24.combustible.pdf
  • 17/06/13: 2do parcial.
  • 19/06/13: Repaso: revisión del parcial.25.parcial.pdf
  • 24/06/13: Recuperatorio.

• 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 – Parte 2

Práctico 2: Tipos abstractos de datos

Práctico 3: Tipos abstractos de datos - Árboles

Práctico 4: algoritmos voraces

Práctico 5: backtracking, programación dinámica y recorrido de grafos

Disponibles en Guarani:

• Primer parcial

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 (ordenado por nombre de alumno) o grupos del lab (ordenado por número de grupo).

• Martes 14 a 18 hs: Teórico del taller, evaluación de entregas si corresponde, 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).

• Manual para hacer tipos abstractos de datos en C: tads-in-c-howto.pdf
• Material sobre punteros (las filminas de la charla): pointers.pdf
• Charla de Makefile: make.pdf

• Proyecto 1: Ordenación, algoritmos elementales y avanzados.
  • Enunciado del proyecto 1
  • Esqueleto del código a completar (versión 0.99.1)
• Proyecto 2: Tipos Abstractos de Datos: Diccionario usando Listas Enlazadas.
  • Enunciado del proyecto 2 - parte A
  • Enunciado del proyecto 2 - parte B
  • Esqueleto del código a completar (para arquitecturas de 64 bits, versión 1.0)
  • Esqueleto del código a completar (para arquitecturas de 32 bits, versión 1.0)
  • Esqueleto del código a completar (para arquitecturas Mac de 64 bits, versión 1.0)
• Proyecto 3: Tipos Abstractos de Datos: Diccionario usando Árboles Binarios de Búsqueda.
  • Enunciado del proyecto 3
• Proyecto 4: Algoritmo de Kruskal.
  • Enunciado del proyecto 4
  • TAD graph y helpers (sin código objeto)
  • Código objeto de heap, priority queue, stack, union find y main - Arquitecturas de 64 bits
  • Código objeto de heap, priority queue, stack, union find y main - Arquitecturas de 32 bits

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.