CI2612: Algoritmos y Estructuras de Datos II (Pregrado)

Blai Bonet
Matemáticas y Sistemas, 215-A
Departamento de Computación
Universidad Simón Bolívar

bonet AT usb DOT ve
Tel: +58 (212) 906-3263
Web: http://www.ldc.usb.ve/~bonet (http://bonetblai.github.io)

Sinopsis

Segundo curso de la cadena de algoritmos y estructuras de datos. Se estudian los temas de ordenamiento y cálculo de estadísticos así como estructuras de datos fundamentales. Se hacen análisis peor caso y caso promedio de algoritmos y del desempeño de operaciones sobre estructuras de datos. Se estudia ordenamiento por inserción, heapsort, quicksort, y los algoritmos lineales count sort, radix sort y bucket sort. Se estudia cotas inferiores para ordenamiento basado en comparaciones y la optimalidad asintótica de heapsort y quicksort con selección de mediana. Se estudian las estructuras de datos elementales de pila, cola, y lista enlazada. Otras estructuras de datos estudiadas son diccionarios (tablas de hash), árboles binarios de búsqueda y árboles rojo negro.

Evaluación (tentativo)

Objetivos y Cronograma (tentativo)

Semana  Día I (Lunes 7-8 en MEM-104) Laboratorio (Martes 7-9 en Sala A y F) Día II (Miércoles 7-8 en MEM-110)
I 18/09: No hay clases. 19/09: Presentación del curso de laboratorio. 20/09: Introducción al curso. Contenido. Evaluación. Bibliografía. Nociones básicas. Algoritmos. Modelo computacional. Complejidad en tiempo y espacio. Crecimiento de funciones. Notación asintótica. Búsqueda lineal y binaria. Ordenamiento por inserción. [§2.1 + §3.1]
II 25/09: Recurrencias. Solución de recurrencias por substitución y Teorema Maestro. Dividir y conquistar. Mergesort. Multiplicación de matrices. Algoritmo de Strassen. Algoritmo de Karatsuba. [§4.1 + §4.2 + §4.3 + §4.4 + §4.5] 26/09: Lab-01. Python. Búsqueda lineal y binaria. Ordenamiento por inserción. Experimentos. Análisis de resultados. 27/09: Probabilidad. Análisis probabilístico. [§5.2 + §5.4 + §C.2 + §C.3]
III 02/10: Algoritmos aleatorizados (randomized algorithms). Algoritmo de Freivalds. [§5.1 + §5.2 + §5.4] 03/10: Lab-02. Mergesort vs. ordenamiento por inserción. Freivalds y disminución del error. 04/10: Introducción a ordenamiento y estadísticos de orden. Heaps. Representación. Heapsort. Colas de prioridad. [Intro. Part II + §6.1 + §6.2 + §6.3 + §6.4 + §6.5]
IV 09/10: Quicksort. Partition. Desempeño de quicksort. Quicksort randomizado. Análisis de peor caso, tiempo esperado y caso promedio. [§7.1 + §7.2 + §7.3 + §7.4] 10/10: Lab-03. Heapsort. Quicksort determinístico y randomizado (versión para datos repetidos). Comparar heapsort, quicksort y mergesort. 11/10: Cotas inferiores para ordenamiento basado en comparaciones. Optimalidad asintótica de mergesort y heapsort. Cotas para tiempo esperado para ordenamiento basado en comparaciones. Optimalidad asintótica de quicksort. Cotas para mezclar listas ordenadas. [§8.1]
V 16/10: Ordenamiento en tiempo lineal. Counting sort. Radix sort. Bucket sort. [§8.2 + §8.3 + §8.4] 17/10: Lab-04. Counting sort y radix sort. Comprar con quicksort randomizado. Dígitos de precisión múltiple. Bucket sort. 18/10: Cálculo de mediana y estadísticos. Máximos y mínimos. Selección del k-ésimo en tiempo lineal esperado. Selección del k-ésimo en tiempo lineal peor caso. [§9.1 + §9.2 + §9.3]
VI 23/10: Repaso. 24/10: Lab-05. Selección del k-ésimo en sus dos variantes (con elementos repetidos). Comparar. 25/10: Examen.
VII 30/10: Conjuntos dinámicos. Estructuras de datos elementales. Pilas y colas. Listas enlazadas. Implementación de apuntadores y objetos. Representación de árboles enraizados. [§10.1 + §10.2 + §10.3 + §10.4] 31/10: Lab-06. ED elementales. Implementar pila con cola y viceversa. Árboles enraizados y algoritmos de recorrido. Experimentos. 01/11: Tablas de hash (diccionarios). Operaciones. Direccionamiento directo. Hashing. Resolución de colisiones por encadenamiento. Funciones de hash. [§11.1 + §11.2]
VIII 06/11: Direccionamiento abierto. Funciones de hash para direccionamiento abierto. [§11.3 + §11.4] 07/11: Lab-07. Hashing con resolución de colisiones por encadenamiento y direccionamiento abierto. Comparar. 08/11: Hashing universal. Hashing perfecto. [§11.5]
IX 13/11: Hashing cuco (cuckoo). Filtro de Bloom. 14/11: Lab-08. Hashing universal y perfecto. Experimentos. 15/11: Árboles binarios de búsqueda. [§12.1 + §12.2 + §12.3]
X 20/11: Árboles rojo negro. [§13.1 + §13.2 + §13.3 + §13.4] 21/11: Quiz 20%. Definición proyecto final. 22/11: Árboles rojo negro. [§13.1 + §13.2 + §13.3 + §13.4]
XI 27/11: Repaso. 28/11: Lab-09. Árboles binarios de búsqueda. 29/11: Examen.
XII 04/12: A definir. 05/12: Entrega proyecto final. 06/12: A definir.

Bibliografía

Last Modified 11 Dic 2017