1151042 Algoritmos y Estructuras de Datos
Trimestre 2013 Otoño
Instructor: Dr. Francisco Javier
Zaragoza Martínez.
Inicio y fin del curso:
lunes 26 de agosto a martes 12 de noviembre 2013.
Grupo: CSI01 (martes y
jueves de 9:15 a 11:30).
Asesorías: lunes, miércoles
y viernes de 15:00 a 16:00 en la oficina H-264.
Salón: E309.
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 ocho tareas. Cada
examen valdrá 6 puntos y cada tarea valdrá 5 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.
27/08:
Inicio
del
curso.
Presentación
del
curso
y
de
las
reglas
de
evaluación.
Tipos de datos abstractos [SW1.1 y SW1.2].
29/08:
Arreglos y apuntadores [KR5.1-5]. Tarea 1
(para el 05/09).
03/09: Estructuras y apuntadores
[KR6.1-7].
05/09: Memoria dinámica [KR6]. Tarea 2 (para el 12/09).
10/09:
Eficiencia de algoritmos iterativos [SW1.4].
12/09:
Pilas y colas [SW1.3].
Tarea 3 (para el 19/09). Guía
para usar su cuenta de callix y enviar la tarea.
17/09: Listas ligadas [SW1.3].
19/09: Clase
cancelada por el paro. Tarea 4
(para el 26/09).
24/09:
Aplicaciones de listas ligadas [SW1.3].
26/09:
Árboles binarios de búsqueda [SW3.2]. Tarea 5 (para el 03/10).
01/10: Árboles balanceados [SW3.3].
Notas de otro curso.
03/10: Aplicaciones de árboles [SW5.2]. Tarea 6 (para el 10/10).
08/10:
Gráficas [SW4.1]
y digráficas [SW4.2].
10/10:
Décimo aniversario de Ingeniería en
Computación. ¡No faltes!
15/10: Árboles abarcadores: Prim y
Kruskal [SW1.5 y
SW4.3].
17/10: Caminos más cortos: Dijkstra y
Warshall [SW4.4].
22/10:
Búsqueda interna: lineal, binaria e interpolación [SW3.1]. Tarea 7 (para el 31/10).
24/10: Ordenamiento
interno: mezcla [SW2.2].
29/10: Ordenamiento interno:
quicksort [SW2.3].
31/10: Ordenamiento interno:
montículo [SW2.4].
05/11:
Ordenamiento de cadenas [SW5.1].
07/11:
Búsqueda de subcadenas [SW5.3].
08/11:
Concurso de
programación ACM-ICPC.
12/11: Examen
global.
12/11: Coloquio Tlahuilcalli: El
hombre que tomaba café, cien años de Paul Erdös.
15/11: Estas
son las
calificaciones finales.
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.