1. (a) ¿Qué es un algoritmo de divide y vencerás? Explicar el enfoque general de los algoritmos de divide y vencerás. (6 puntos)
(b) Utilice el enfoque de divide y vencerás para diseñar un algoritmo que encuentre el elemento mínimo en una matriz de n elementos. Analice la complejidad temporal de su algoritmo. (10 puntos)
2. (a) Explique el concepto de técnicas de resolución de colisiones y hash. (6 puntos)
(b) Considere una tabla hash de tamaño m y un conjunto de n elementos a los que se les aplicará el hash. Suponga que los elementos están distribuidos uniformemente entre las m ranuras. ¿Cuál es la probabilidad de una colisión cuando n =m/2? Analice el número promedio de comparaciones necesarias para insertar con éxito todos los elementos en la tabla hash mediante sondeo lineal. (10 puntos)
3. (a) Describa el concepto de programación dinámica y explique en qué se diferencia del enfoque de divide y vencerás. (6 puntos)
(b) Utilice programación dinámica para resolver el problema de corte de varillas, donde una varilla de longitud n se puede cortar en varillas más pequeñas y cada varilla de longitud i tiene un precio p[i]. El objetivo es encontrar el ingreso máximo que se puede obtener cortando la varilla en pedazos más pequeños. Analice la complejidad temporal y espacial de su algoritmo. (10 puntos)
4. (a) Explique el concepto de completitud NP y su importancia en el análisis de algoritmos. (6 puntos)
(b) Demuestre que el siguiente problema es NP-completo:Dado un conjunto de n elementos con sus respectivos pesos y valores, determine si existe un subconjunto de estos elementos cuyo peso total sea menor o igual a un límite dado y cuyo peso total sea menor o igual a un límite dado. el valor se maximiza. (10 puntos)
5. (a) Explique el concepto de análisis amortizado de algoritmos. ¿Por qué se utiliza y cuáles son sus beneficios? (6 puntos)
(b) Realice un análisis amortizado de la estructura de datos de la pila, donde las operaciones push y pop son las únicas operaciones permitidas. Determine la complejidad temporal promedio de cada operación. (10 puntos)
6. (a) Describa el algoritmo de Kruskal para encontrar el árbol de expansión mínimo de un gráfico no dirigido ponderado. (6 puntos)
(b) Aplique el algoritmo de Kruskal al siguiente gráfico y encuentre el árbol de expansión mínimo:
```
(1)---2---(3)
/ |
/ |
5 / 4
-----------
(4)---6---(5)
```
Calcule el peso total del árbol de expansión mínimo. (10 puntos)
7. (a) Explique el concepto de tipo topológico de gráfico acíclico dirigido (DAG). (6 puntos)
(b) Realice una clasificación topológica en el siguiente DAG:
```
(1) -> (2) -> (3)
\ /
-> (4)
```
Proporcione el orden de los vértices en la clasificación topológica. (10 puntos)
8. (a) Describa el concepto de árboles de búsqueda binarios (BST). Explique cómo se utilizan las BST para operaciones eficientes de búsqueda e inserción. (6 puntos)
(b) Inserte los siguientes elementos en un BST inicialmente vacío:20, 10, 30, 5, 15, 25, 35. Dibuje el BST resultante y analice la complejidad temporal de buscar un elemento en este BST. (10 puntos)
Recuerde demostrar una comprensión clara de los conceptos, brindar explicaciones correctas y analizar las complejidades temporales y espaciales de los algoritmos cuando sea necesario.