Algoritmos y Estructuras de Datos II

• Docentes:
  • Teóricos: Daniel Fridlender
  • Prácticos: Walter Alini, Diego Lis, Alejandro Tiraboschi
    • Ayudantes: Germán Ceballos, Franco Rodríguez Fábregues
  • Taller: Damian Barsotti, Martín Domínguez, Diego Dubois, Natalia Bidart.
    • Ayudantes: Florencia Mihaich, Cesar Bernardini, Leonardo Rodriguez, Ezequiel Velez.

• Parciales: 3 (fechas preliminares: 7/4/10, 10/5/10 y 16/6/10).
• 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.

• 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.

• Notas de Algoritmos y Estructuras de Datos II.
  • Primera parte ( Análisis de algoritmos)
  • Segunda parte ( Estructuras de datos)
  • Tercera parte ( Técnicas de diseño de algoritmos)
  • Tercera parte, extensión ( Branch \& Bound)
• 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

• Otros
  • Object-Oriented Programming Versus Abstract Data Types

• Parte 1: Análisis de algoritmos.
  • Lunes 08/03: Presentación, motivación, ordenación por selección, conteo.
  • Miércoles 10/03: Método para contar operaciones, ordenación por inserción, peor caso, mejor caso y caso medio.
  • Lunes 15/03: Notación O. Definición, propiedades. Regla del límite. Jerarquía de funciones.
  • Miércoles 17/03: Jerarquía de funciones. Notación complementaria. Equivalencias. Búsqueda lineal y binaria. Ordenación por intercalación.
  • Lunes 22/03: Análisis de la ordenación por intercalación para potencias de 2. Funciones eventualmente no decrecientes. Funciones i-suaves, funciones suaves. Ejemplos. Ordenación por intercalación. Recurrencias divide y vencerás. Análisis de una versión recursiva de la búsqueda binaria.
  • Miércoles 24/03: Feriado.
  • Lunes 29/03: Ejemplos de recurrencias divide y vencerás. Recurrencias homogéneas. Ejemplos. Método general. Demo de ordenación.
  • Miércoles 31/03: Recurrencias no homogéneas. Método general. Ejemplos (entre ellos: comparaciones del algoritmo de intercalación).
• Parte 2: Estructuras de datos.
  • Lunes 05/04: Estructuras de datos: concretas (demo) vs. abstractas. Estructuras concretas: arreglos, listas, tuplas, punteros. Estructuras abstractas: paréntesis balanceados (TAD contador).
  • Miércoles 07/04: Primer parcial.
  • Lunes 12/04: Generalización de paréntesis balanceados (TAD pila), especificación, pila y recursión, implementaciones habituales. En el práctico: clase del TAD cola, implementaciones con listas y con arreglos.
  • Miércoles 14/04: TAD cola: repaso e implementaciones. Listas enlazadas. Pilas con listas enlazadas, demo.
  • Lunes 19/04: Implementación de colas con listas enlazadas. Con dos punteros. Con listas circulares. TAD lista. TAD árbol binario, introduccion.
  • Miércoles 21/04: Árboles binarios de búsqueda, implementación de diccionarios.
  • Lunes 26/04: Cola de prioridades y heaps. Heapsort.
• Parte 3: Técnicas de diseño de algoritmos.
  • Miércoles 28/04: Heapsort. Desarrollos top-down y bottom-up. Algoritmos divide y vencerás. Características. Ejemplos. Forma general. Quicksort (ordenación rápida), clasificar, elección del pivot.
  • Lunes 03/05: Divide y vencerás: Ejemplo de quicksort. Exponenciación. Multiplicación de números grandes. Algoritmos voraces: problema de la moneda, problema de la mochila.
  • Miércoles 05/05: Algoritmos voraces: algoritmo de Dijkstra.
  • Lunes 10/05: Segundo parcial.
  • Miércoles 12/05: Algoritmos voraces: árbol generador de costo mínimo. Prim. Kruskal. Problema Union-Find.
  • Lunes 17/05: Programación dinámica (y backtracking). Fibonacci. Problema de la moneda. Problema de la mochila.
  • Miércoles 19/05: Programación dinámica (y backtracking). Algoritmo de Floyd. Funciones con memoria. Inicialización virtual.
  • Lunes 31/05: Inicialización virtual. Recorrida de árboles binarios y finitarios
  • Miércoles 02/06: Recorrida de grafos, dfs y bfs
  • Lunes 07/06: Backtracking.
  • Miércoles 09/06: Branch & Bound.
  • Lunes 14/06: Branch & Bound.

• Algoritmos de ordenación.
  • en wikipedia
  • Algunos visualizadores
    • sorting-demo.html
    • xSortLab
    • index.sv.shtml
    • VisuTri
• Notación O
  • en wikipedia
  • Algunos visualizadores
    • graphing.html
    • index.html
    • function-graphs
• TADs
  • Algunos visualizadores
    • Pilas y colas download.html
    • Árboles binarios AVL

• Lunes 8/3: éste es el primer práctico.

• Miércoles 10/3: éste es el segundo práctico.

• Lunes 22/3: éste es el tercer práctico.

• Lunes 12/4: éste es el cuarto práctico.

• Miércoles 28/4: éste es el quinto práctico.

• Miércoles 12/5: éste es el sexto práctico.

• Lunes 17/5: éste es el séptimo práctico.

• Miércoles 26/5: éste es el octavo práctico.

• Lunes 7/6: éste es el noveno práctico.

• Martes 14 a 18 hs: Uso reservado para prácticas libres de alumnos de la materia.
• Jueves 14 a 18 hs: Teórico del taller y consultas.

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

Modelos de memoria

Punteros en C

Funciones malloc calloc free

• Proyecto 1 primera parte: Programas con punteros y memoria dinámica.

• Proyecto 1 segunda parte: TAD Diccionario con lista de asociaciones en arreglos.

• Proyecto 2 primera parte: TAD lista con lista enlazada en C.

• Proyecto 2 segunda parte: TAD Diccionario con lista de asociaciones en cinta de tuplas. Librería de cinta de escritura y lectura de tuplas en archivos ☛ libcrw.

• Proyecto 3: Diccionario sobre ABB. Makefile genérico.

• Proyecto 4: Kruskal. Se brinda además un archivo .dot con el grafo de ciudades y distancia entre ellas, mas una tabla que mapea que número de nodo corresponde a que ciudad y un script para generar el archivo pdf ejecutando neato. Con el programa del proyecto calcular el mínimo tendido de fibra óptica para interconectar las ciudades.

Ir a la página de la lista y llenar los datos.

o

Enviar un mail a:

alualgo2-join@famaf.unc.edu.ar

con cualquier subject o cuerpo del mail.

Despues de enviarlo debe llegar un mail donde diga que la subscripcion fue realizada correctamente. Hacer un reply con el mismo subjet (pero que no diga Re: —).

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.