Análisis de Algoritmos y Estructuras de Datos

Semestre 2008-1, UNAM

Agosto a Diciembre, 2007

Página principal del curso

Profesor: Sergio Rajsbaum

Ayudante: Jorge Figueroa <jfigueroac@uxmcc2.iimas.unam.mx>

Curso impartido a alumnos de la Maestría en Ciencia e Ingeniería de la Computación como Estructuras de Datos y Teoría de Algoritmos.

Lugar: Aula 201, edificio anexo del IIMAS.

Horario: Martes y Jueves, de 10:00 a 11:30 hrs. 

Contenido de esta página

• Forma de trabajo
• Contacto con Profesores y Ayudantes
• Tareas
• Exámenes
• Clases
  

Forma de trabajo

Durante el curso se dejarán tareas y consistirán en ejercicios relacionados con los temas tratados en clase. Cada tarea tendrá que ser resuelta en un plazo fijo. La fecha de entrega es estricta. Se pueden realizar en equipos de a lo más 2 personas, pero cada una debe entregarla por separada e indicando en nombre de su compañero de equipo.
Los exámenes incluirán preguntas tomadas directamente de las tareas.

Contacto con el Profesor y el Ayudante

Profesor:

• Sergio Rajsbaum
  Instituto de Matemáticas
  email: rajsbaum@matem.unam.mx

Ayudante:

• Jorge Figueroa
  Oficina:
  email: jfigueroac@uxmcc2.iimas.unam.mx

Tareas

Las tareas estarán disponibles conforme se vayan dejando durante el curso. La fecha de entrega es estricta.

• Tarea 1: 23 de agosto 2007, entrega 30 de agosto 2007
  
• Coloración
• Tarea 2: 5 de septiembre 2007, entrega 18 de septiembre 2007
  
• Coloración, notación asintótica, apareamientos estables, lectura Dijkstra de Out of Their Minds
  
• Tarea 3: 24 de septiembre 2007, entrega 4 de octubre 2007 (se pospuso al 9 de octubre)
  
• Apareamientos estables, calendarización, Donald Knuth "Sand Piles and Spanning Trees"
• Tarea 4: 9 de octubre 2007, entrega 18 de octubre 2007
  
• Algoritmos greedy, Heaps Binarios, lectura Rabin y Knuth de Out of Their Minds
• Tarea 5: 24 de octubre 2007, entrega 6 de noviembre 2007
  
• Algoritmos merge, divide y vencerás, lectura Tarjan y Lamport de Out of Their Minds
• Tarea 6: 13 de noviembre 2007, entrega 22 de noviembre 2007
  
• Algoritmos distribuidos, flujo en redes, lectura Cook-Levin de Out of Their Minds
• Tarea 7: 22 de noviembre 2007, entrega 4 de diciembre 2007
  
• flujo en redes, conexidad, apareamientos
  

Exámenes

• Examen Final: jueves 13 de diciembre 10 a 11:30
  

Clases. Libro de texto: Algorithm Design de Kleinberg y Tardos.

• Primer día de clases, agosto 14, 2007
• martes y jueves agosto 14 y 16: clases con el ayudante (Sergio fueras en PODC) acerca de gráficas
• martes agosto 21: inducción y coloración
• jueves agosto 23: algortmo exponencial de 6-coloración y representación de gráficas
• martes agosto 28: algortmo lineal de 6-coloración
• jueves agosto 30: notación asintótica
• martes septiembre 4: apareamientos estables
• jueves septiembre 6: apareamientos estables
• martes septiembre 11: gráficas, árboles y BFS
• jueves septiembre 13: BFS, gráficas bipartitas, gráficas dirigidas y fuertemente conexas
  
• martes septiembre 18: calendarización de intervalos (sec. 4.1 del libro)
  
• jueves septiembre 20: particionamiento de intervalos (sec. 4.1 del libro)
• martes septiembre 25: en lugar de la clase, conferencia de Lorenzo Alvisi "Bar Gossip", lunes 24 a la 1:15pm
• jueves septiembre 27: estoy en LADC y ENC en Morelia, en lugar de clase ver clase de Donald Knuth Sand Piles and Spanning Trees
• martes octubre 2: Algoritmo de Dijkstra
  
• jueves octubre 4: Heaps Binarios
• martes octubre 9: Árboles generadores mínimos
  
• jueves octubre 11: ejercicios de algoritmo de Prim y Kruskal. Introducción a Heaps Binomiales. Impartida por Jorge Figueroa.
• martes octubre 16: Divide y Vencerás. Merge Sort. Merge sin espacio adicional.
  
• jueves octubre 18: Contando inversiones
  
• martes octubre 23: Algoritmo de parejas de puntos más cercanos
• jueves octubre 25: Programación dinámica. Caminos más cortos y Bellman-Ford
• martes octubre 30: Algoritmos Distribuidos- impartida por Michel Raynal
• miércoles octubre 31:2nda parte clase de Michel. Relojes lógicos y exclusión mutua
  
• jueves noviembre 1: no hay labores
• martes noviembre 6: algoritmos distribuidos, consenso síncrono- impartida por Corentin Travers
• jueves noviembre 8: Tiempo y algoritmos distribuidos
• martes noviembre 13: Flujo en redes 1
  
• jueves noviembre 15: Flujo en redes 2 (apareamientos máximos en gráficas bipartitas)
• martes noviembre 20: Flujo en redes 3 (apareamientos máximos en gráficas bipartitas, Teorem de Hall, caminos disjuntos)
• jueves noviembre 22: Flujo en redes 4 (Flujos con requerimientos de producción y demanda en nodos, con cotas inferiores en arcos)
• martes noviembre 27:
• jueves noviembre 29: Último día de clases