====== 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: [[http://www.cs.famaf.unc.edu.ar/~damian|Damian Barsotti]], Martín Domínguez, Diego Dubois, Natalia Bidart. * Ayudantes: Florencia Mihaich, Cesar Bernardini, Leonardo Rodriguez, Ezequiel Velez. ===== Generalidades ===== * 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. === 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 ({{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/parte1.pdf | Análisis de algoritmos}}) * Segunda parte ({{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/parte2.pdf | Estructuras de datos}}) * Tercera parte ({{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/parte3.pdf | Técnicas de diseño de algoritmos}}) * Tercera parte, extensión ({{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/parte3b.pdf | 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, {{http://www.cs.famaf.unc.edu.ar/~damian/algoritmos1/apunte/main.pdf|Cálculo de Programas}}. * Tutoriales de lenguaje C * {{algo2:cursc.html | En castellano pero básico}} * [[http://www.cs.cf.ac.uk/Dave/C/ | En ingles pero muy completo]] * [[http://www.space.unibe.ch/comp_doc/c_manual/C/cref.html|Manual de referencia en inglés]] * Otros * {{algo2:main:cookoopvsadt90.pdf|Object-Oriented Programming Versus Abstract Data Types}} ==== Clases ==== * 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. ==== Vínculos interesantes ==== * Algoritmos de ordenación. * {{http://en.wikipedia.org/wiki/Sorting_algorithms | en wikipedia}} * Algunos visualizadores * {{http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html}} * {{http://math.hws.edu/TMCM/java/xSortLab/}} * {{http://www.ida.liu.se/~TDDB28/mtrl/demo/sorting/index.sv.shtml}} * {{http://thomas.baudel.name/Visualisation/VisuTri/}} * Notación //O// * {{http://en.wikipedia.org/wiki/O_notation | en wikipedia}} * Algunos visualizadores * {{http://www.math.com/students/graphing.html}} * {{http://www.coolmath.com/graphit/index.html}} * {{http://rechneronline.de/function-graphs/}} * TADs * Algunos visualizadores * Pilas y colas {{http://www.cs.usfca.edu/~galles/visualization/download.html}} * Árboles binarios {{http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm|AVL}} ===== Práctico ===== * Lunes 8/3: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico1.pdf | primer práctico}}. * Miércoles 10/3: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico2.pdf | segundo práctico}}. * Lunes 22/3: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico3.pdf | tercer práctico}}. * Lunes 12/4: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico4.pdf | cuarto práctico}}. * Miércoles 28/4: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico5.pdf | quinto práctico}}. * Miércoles 12/5: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico6.pdf | sexto práctico}}. * Lunes 17/5: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico7.pdf | séptimo práctico}}. * Miércoles 26/5: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico8.pdf | octavo práctico}}. * Lunes 7/6: éste es el {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/practico9.pdf | noveno práctico}}. ===== Laboratorio ===== ==== Horarios ==== * 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. ==== Clases ==== === 9/03: === Modelos de memoria Punteros en C Funciones malloc calloc free ==== Proyectos ==== * {{:algo2:main:2010:proy01_parte1.pdf|Proyecto 1 primera parte}}: Programas con punteros y memoria dinámica. * {{:algo2:main:2010:proy01_parte2.pdf|Proyecto 1 segunda parte}}: TAD Diccionario con lista de asociaciones en arreglos. * {{:algo2:main:2010:proy02_parte1.pdf|Proyecto 2 primera parte}}: TAD lista con lista enlazada en C. * {{:algo2:main:2010:proy02_parte2.pdf|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 ☛ {{:algo2:main:2010:libcrw.tgz|libcrw}}. * {{:algo2:main:2010:proy03.pdf|Proyecto 3}}: Diccionario sobre ABB. {{:algo2:main:2010:makefile.gz|Makefile}} genérico. * {{:algo2:main:2010:kruskal.pdf|Proyecto 4}}: Kruskal. Se brinda además un {{:algo2:main:2010:mapa.tgz|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. ==== Notas del Taller ==== ===== Instrucciones para inscribirse en la lista de mails ===== Ir a la [[http://agni.famaf.unc.edu.ar/cgi-bin/mailman/listinfo/alualgo2|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: ---). === !! 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.