Ciencias de la Computación FAMAF

Esta página es de solo lectura. Puedes ver la fuente pero no puedes cambiarla. Pregunta a tu administrador si crees que esto es incorrecto.
====== Algoritmos y Estructuras de Datos II ======

  * Docentes:
    * Teóricos: Daniel Fridlender
    * Prácticos: Juan Durán, Sergio Giro, Alejandro Tiraboschi.
    * Taller: [[http://www.cs.famaf.unc.edu.ar/~damian|Damian Barsotti]], Marcos Dione, Martín Domínguez.
    * Ayudantes: FIXME


===== Generalidades =====

  * Parciales: 3 (fechas preliminares: 16/4, 14/5 y 18/6).
  * 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/aclase0801.pdf | Primeras dos clases}} y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0801.pdf | preguntas}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0802.pdf | Tercer y cuarta clases}} y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0802.pdf | preguntas}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0803.pdf | Quinta y sexta clases}} y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0803.pdf | preguntas}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0804.pdf | Recurrencias divide y vencerás}} (sexta clase) y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0804.pdf | preguntas}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0805.pdf | Recurrencias lineales homogéneas}} (séptima clase) y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0805.pdf | preguntas}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0806.pdf | Recurrencias no homogéneas}} (octava clase) y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0806.pdf | preguntas}}.
          * Segunda parte
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0807.pdf | Novena clase}} y sus {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/preguntas/pclase0807.pdf | preguntas}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0808.pdf | Décima y décimoprimera clases}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0809.pdf | Décimosegunda clase}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0810.pdf | Décimotercera, décimocuarta y décimoquinta clases}}.
          * Tercera parte
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0811.pdf | Decimosexta y decimoséptima (media) clases}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0812.pdf | Decimoséptima (media) y decimooctava clases}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0813.pdf | Decimonovena y vigésima clases}}.
                 * {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/apuntes/aclase0814.pdf | Vigésimoprimera clase}}.
    * 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 ====

    * 01: (10/03/08 y 12/03/08) Presentación, motivación, ordenación por selección, conteo, ordenación por inserción.
    * 02: (17/03/08 y 19/03/08) Notación //O//, propiedades, regla del límite, jerarquía de funciones, notación complementaria.
    * 03: (26/03/08 y 31/03/08) Búsqueda lineal y binaria, ordenación por intercalación.
    * 04: (31/03/08) Recurrencias divide y vencerás.
    * 05: (07/04/08) Recurrencias lineales homogéneas.
    * 06: (09/04/08) Recurrencias no homogéneas.
    * 07: (14/04/08) Estructuras concretas/abstractas de datos. Estructuras concretas: arreglos, listas, tuplas, punteros.
    * 08: (21/04/08 y 23/04/08) Tipos abstractos de datos: pilas, colas y listas.  Implementaciones de pilas y colas usando arreglos y listas.
    * 09: (28/04/08) Listas enlazadas, implementación de pilas y colas.
    * 10: (30/04/08, 05/05/08 y 07/05/08) Árboles binarios. Árboles binarios de búsqueda. TAD cola de prioridades. Heap.
    * 11: (12/05/08 y 26/05/08 (media)) Algoritmos divide y vencerás.
    * 12: (26/05/08 (media), 28/05/08 y 02/06/08) Algoritmos voraces.
    * 13: (04/06/08, 09/06/08 y 11/06/08) Programación dinámica.
    * 14: (18/06/08) Recorrida de grafos y backtracking.

==== 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://www.geocities.com/siliconvalley/network/1854/Sort1.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/}}
    * Árboles binarios
          * Algunos visualizadores
                 * {{http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm}}

===== Práctico =====
  * Éste es el práctico correspondiente a toda la materia: {{http://www.cs.famaf.unc.edu.ar/~fridlend/cursos/algoritmos2/ejercicios/ejercicios2008.pdf | Práctico 2008}}.


===== Laboratorio =====




==== Horarios ====

  * Lunes 9 a 13 hs: Consultas y correciones de proyectos.
  * Viernes 14 a 16 hs: Teórico del laboratorio.
  * Viernes 16 a 18 hs: Consultas y práctica libre.

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



















==== Clases ====

  * 14/3: Revisión de distintas zonas de memoria al ejecutarse un programa. Memoria dinámica. Implementación de TAD's en memoria dinámica. Constructores, destructores y funciones que clonan. Ejemplo completo TAD Par usando la técnica. Lanzamiento proyecto 1.

  * 28/3: Implementación de listas con punteros. Implementacion de constructores y metodos sobre listas (tipo haskell). Problemas de memory leaks y punteros colgados en función tail.

  * 4/4: Cinta de elementos para manipular listas enlasadas (con inserción en posicion corriente y borrado del elemento corriente). Especificación abstracta con pre y post. Implementación con puntero a parte derecha (''c->pd''). Problema para insertar y borrar. Implementacion con nodo dummy dentro de la estructura (''c->cd''), puntero a uno antes de la parte derecha  (''c->ppd'').

  * 11/4: Makefile exhaustivo.

  * 18/4: Manejo de errores. Errores de sintaxis, de lógica y de sistema. Variable ''errno'', funciones ''strerror'', ''perror'', ''err'', ''warn'', ''errx'', ''warnx''. Librería ''assert''. 

  * 25/4: Implementaciones de mapas y conjuntos. Hash abierto.

  * 2/5: Implementación arboles binarios de buzqueda en C  primera parte. Versiones recursivas e iterativas. Uso de pre y pos condiciones y versiones funcionales para diseñar y probar algorítmos. 

  * 9/5: Implementación arboles binarios de buzqueda en C  segunda parte. Desarrollo de función add iterativa usando anotaciones.

  * 16/5: Implementación de AVL.

  * 29/5: Kruskal con TAD's para proyecto. Abstracción de ''streams'' en C.
















==== Proyectos ====

  * {{algo2:main:2008:proy01.pdf|Proyecto 1: Diccionario sobre lista de asociaciones}}.
  
  * {{algo2:main:2008:proy02.pdf|Proyecto 2: Cintas}}. {{algo2:main:2008:libcrw.tgz|Descargar}} cintas de lectura y escritura de tuplas en disco. {{algo2:main:2008:diccionario.dic.gz|Descargar}} diccionario de prueba. {{algo2:main:2008:makefile_generico.gz|Descargar}} make file genérico (tiene además todos los parametros de deteccion de errores para el gcc).

  * {{algo2:main:2008:proy03.pdf|Proyecto 3: Hash}}.

  * {{algo2:main:2008:proy04.pdf|Proyecto 4: Abb}}.

  * {{algo2:main:2008:kruskal.pdf|Proyecto 5: Kruskal}}.

===== Instrucciones para inscribirse en la lista de mails =====

Enviar un mail a:

  minimalist@hal.famaf.unc.edu.ar

con el subject:

  subscribe alualgo2

El cuerpo del mail se puede dejar en blanco.

Despues de enviarlo debe llegar un mail donde diga que la subscripcion fue realizada correctamente.

=== !! 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.