| Semana |
Día I (Lunes 7-8 en ENE-104) |
Día II (Miércoles 7-8 en ENE-110) |
| I |
23/04:
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] |
25/04:
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] |
| II |
30/04:
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] |
02/05:
Probabilidad. Análisis probabilístico. [§5.2 + §5.4 + §C.2 + §C.3] |
| III |
07/05:
Algoritmos aleatorizados (randomized algorithms).
Algoritmo de Freivalds.
[§5.1 + §5.2 + §5.4] |
09/05:
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] |
| IV |
14/05:
Solución de problemas. |
16/05:
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 |
21/05:
Ordenamiento en tiempo lineal.
Counting sort.
Radix sort.
Bucket sort.
[§8.2 + §8.3 + §8.4] |
23/05:
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 |
28/05:
Repaso. |
30/05:
Examen. |
| VII |
04/06:
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] |
06/06:
Tablas de hash (diccionarios).
Operaciones.
Direccionamiento directo.
Hashing.
Resolución de colisiones por encadenamiento.
Funciones de hash.
[§11.1 + §11.2] |
| VIII |
11/06:
Tablas de hash (diccionarios).
Direccionamiento abierto.
Funciones de hash para direccionamiento abierto.
[§11.3 + §11.4] |
13/06:
Hashing universal.
Hashing perfecto.
[§11.5] |
| IX |
18/06:
Solución de problemas.
| 20/06:
Hashing cuco (cuckoo).
Filtro de Bloom. |
| X |
25/06:
No hay clases.
| 27/06:
Árboles binarios de búsqueda.
[§12.1 + §12.2 + §12.3] |
| XI |
02/07:
Árboles rojo negro.
[§13.1 + §13.2 + §13.3 + §13.4] |
04/07:
Repaso.
Resolución de problemas. |
| XII |
09/07:
Examen. |
11/07:
No hay clases. |