| Semana |
Día I |
Día II |
| | |
| I |
Presentación y evaluación. Requisitos.
Crecimiento asintótico y teorema maestro.
Teoría de probabilidad (nivel básico). |
Cotas inferiores absolutas para ordenamiento:
peor caso y caso promedio. Heapsort. |
| II |
Quicksort. Ordenamiento lexicográfico.
Mediana y otros estadísticos. |
Introducción a las estructuras de datos (ED).
ED elementales. Representación. |
| III |
Hashing: "chaining" y abierto (universal*). |
Árboles binarios de búsqueda. |
| IV |
Árboles rojo-negro. |
Programación dinámica. Multiplicación de Matrices. |
| V |
Algoritmos greedy. Selección de actividades y códigos de Huffman. |
Análisis amortizado. |
| VI |
Mergeable heaps: binomial y Fibonacci. |
Conjuntos disjuntos: Union/Find. |
| VII |
Algoritmos en grafos. Representación.
Búsqueda en amplitud (BFS). |
Búsqueda en profundidad (DFS). Ordenamiento
topológico. Componentes fuertemente conectadas. |
| VIII |
Árbol cobertor mínimo (MST).
Algoritmos de Kruskal y Prim. |
Caminos de costo mínimo. Operaciones básicas:
Inicialización y Relajación. Grafos de predecesores.
|
| IX |
Algoritmos para vértice "fuente": Dijkstra y Bellman-Ford. |
Algoritmos para todos los pares: Floyd-Warshall y Johnson. |
| X |
Flujo máximo. |
Flujo máximo. |
| XI |
Examen. |
|
| XII |
|
|