1151042 Algoritmos y Estructuras de Datos
Trimestre 2014 Primavera
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 21 de abril a miércoles 9 de julio de 2014.
Grupo: CSI01 (lunes,
miércoles y viernes de 11:30 a 13:00).
Asesorías: lunes, miércoles
y viernes de 9:00 a 10:00 en la oficina H-264.
Salón: G208.
Cupo: 50 alumnos.
Contenido
Se cubrirá el contenido
oficial del curso (el cual se detalla abajo). Es posible que
el temario se cubra en un orden distinto al allí mencionado.
- Tipos de datos abstractos y estructuras dinámicas.
- Recursividad y eficiencia.
- Estructuras para listas.
- Estructuras para árboles.
- Estructuras para gráficas.
- Algoritmos de búsqueda interna.
- Algoritmos de ordenamiento interno.
- Algoritmos de procesamiento de cadenas.
Evaluación
Habrá al menos diez exámenes semanales y al menos diez tareas. Cada
examen valdrá 6 puntos y cada tarea valdrá 4 puntos. No habrá examen
global. Se requiere obtener
- al menos 30 puntos en los exámenes, 20 puntos en las tareas y
un total de al menos 60 puntos para acreditar con S,
- al menos 35 puntos en los exámenes, 25 puntos en las tareas y
un total de al menos 73 puntos para acreditar con B y
- al menos 40 puntos en los exámenes, 30 puntos en las tareas y
un total de al menos 87 puntos para acreditar con MB.
Las tareas se deberán entregar por correo electrónico a la cuenta aed en callix.azc.uam.mx y deberán estar escritas en C. Su
cuenta está en la misma máquina, a la que se pueden conectar con ssh. Recuerden que, de acuerdo al
Reglamento de
Alumnos de la UAM, es falta de los alumnos en contra de la
Institución el suplantar o permitir ser suplantado en la realización
de actividades académicas (Artículo 9) y se impondrá desde
amonestación escrita hasta suspensión por dos trimestres (Artículo
13).
Calendario
El calendario de clases, de entrega de tareas y de evaluaciones que
muestro abajo es tentativo e irá apareciendo paulatinamente. He
anotado los capítulos y secciones correspondientes del Sedgewick y
Wayne [SW] y del Kernighan y Ritchie [KR] a la derecha de cada tema.
Guía para usar su cuenta de callix.
21/04:
Inicio del curso. Presentación del curso y de las reglas de
evaluación. Tipos de datos concretos y abstractos [SW1.1 y SW1.2].
23/04:
Memoria y apuntadores [KR5.1-2].
25/04:
Arreglos y apuntadores [KR5.3-5]. Tarea 1
(para el 02/05) y calificaciones.
28/04: Estructuras y apuntadores
[KR6.1-4, 6.7].
30/04: Memoria dinámica [KR6.5].
02/05: Recursión lineal. Tarea 2 (para el 09/05) y calificaciones.
05/05:
Día feriado.
07/05:
Recursión binaria.
09/05:
Eficiencia de algoritmos iterativos y recursivos [SW1.4]. Tarea 3 (para el 16/05) y calificaciones.
12/05: Pilas [SW1.3].
14/05: Colas [SW1.3].
16/05: Listas ligadas [SW1.3]. Tarea 4 (para el 23/05) y calificaciones.
19/05:
Aplicaciones de listas ligadas [SW1.3 y SW3.1].
21/05:
Árboles binarios de búsqueda [SW3.2]. Tarea 5 (para el 26/05) y calificaciones.
23/05:
Árboles binarios de búsqueda [SW3.2].
26/05: Inicia el examen calificatorio
del XI
Concurso de programación de la UAM (corresponde con las
tareas adicionales A, B y C).
26/05: Árboles binarios de búsqueda [SW3.2].
28/05: Árboles balanceados [SW3.3].
Notas de otro curso.
30/05: Árboles balanceados [SW3.3].
31/05: Termina el examen
calificatorio del XI Concurso de programación de la UAM.
02/06:
Gráficas [SW4.1].
04/06:
Digráficas [SW4.2].
06/06:
Recorridos de gráficas y digráficas [SW4.1 y SW4.2]. Tarea 6 (para el 09/06) y calificaciones.
09/06: Inicia el examen eliminatorio
del XI
Concurso de programación de la UAM (corresponde con las
tareas adicionales D, E y F).
09/06: Árboles abarcadores: Algoritmo
de Prim [SW1.5 y
SW4.3].
11/06: Caminos más cortos: Algoritmo
de Dijkstra [SW4.4].
13/06: No
habrá clase.
16/06:
Termina el examen eliminatorio del XI Concurso de programación de
la UAM.
16/06:
Búsqueda interna: lineal, binaria e interpolación [SW3.1]. Tarea 7 (para el 23/06).
18/06:
Búsqueda interna: tablas de dispersión [SW3.4].
20/06: Ordenamiento
interno: elementales [SW2.1].
23/06: Ordenamiento interno: mezcla [SW2.2]. Tarea 8 (para el 30/06) y calificaciones.
25/06: Ordenamiento interno:
quicksort [SW2.3].
27/06: Ordenamiento interno:
montículo [SW2.4].
30/06:
Ordenamiento de cadenas [SW5.1].
02/07:
Tries [SW5.2].
Tarea 9 (para el 07/07).
04/07:
Búsqueda de subcadenas [SW5.3].
07/07: Fin del curso.
09/07: Examen final.
Bibliografía
- Aho, Ullman y Hopcroft. Estructuras de datos y algoritmos.
Pearson.
- Harvey. Computer Science Logo Style. Volumes 1,
2,
3.
MIT Press.
- Kernighan y Ritchie. El lenguaje de programación C. Pearson.
- Knuth.
The
Art of Computer Programming: Vol. 3 Sorting and Searching.
Addison Wesley.
- Llana, et al. Ejercicios
de programación creativos y recreativos en C++. Prentice
Hall.
- Sedgewick.
Algoritmos en C++. Pearson.
- Sedgewick y Wayne. Algorithms.
Pearson.