Cinvestav
Departamento de Computación

Curso: Análisis y Diseño de Algoritmos

Prof. Dr. Luis Gerardo de la Fraga
Cuatrimestre agosto a diciembre de 2024

Este es el contenido del curso.

Apuntes del Curso:

1. El pseudocódigo para insertar y borrar un nodo en un árbol rojo y negro.
   
2. Visualización de árboles binarios con Graphviz.
   
3. Realización de un árbol de búsqueda binario en python.
   
4. Realización de un montón en python.
   
5. Prueba de que una variable aleatoria tiene una distribución gausiana.
   
6. El problema del subarreglo máximo.
   
7. Ordenamiento de puntos de forma circular.
   
8. Código en python del algoritmo de ordenamiento por inserción.
   El peor tiempo de ejecución es Theta(n^2)
9. Código en python para el trazo de la línea según el algoritmo del punto medio.
10. Código en python para el trazo de la línea.

Tareas del Curso:

Tarea 8: Creación de un árbol rojo y negro
Fecha de entrega: martes 26 de noviembre, 2024

1. Programar en python un árbol rojo y negro y las operaciones sobre el árbol: buscar(), minimo(), maximo(), predecesor, sucesor(), insertar_rn() y borrar_rn().
2. A partir de un arreglo de llaves diferentes, revuelve aleatoriamente las llaves y cree un árbol rojo y negro usando la operación de insertar_rn() recorriendo incrementalmente las llaves del arreglo.
3. Visualize tres árboles distintos creados con el procedimiento del punto anterior.
4. Sobre un árbol rojo y negro borre tres nodos distintos, visualize el resultado y verifique que el resultado sigue siendo un árbol rojo y negro.

Tarea 7: Creación de un árbol de búsqueda binario
Fecha de entrega: jueves 14 de noviembre, 2024

1. A partir de un arreglo ordenado de llaves haga la subrutina para crear un árbol de búsqueda binario con la altura mínima
2. Utilize las operaciones vistas en clase sobre un árbol de búsqueda binario.

Tarea 6: Estadísticas de orden
Fecha de entrega: martes 5 de noviembre, 2024

1. Programar la rutina para encontrar el mínimo y máximo de un conjunto de n elementos que ocupe a lo más 3 piso(n/2) comparaciones.
2. Implemente la rútina para encontrar la mediana en tiempo lineal.
3. Realize las pruebas necesarias pare mostrar que su ejecución en lineal

Tarea 5: Ordenamiento del montón
Fecha de entrega: jueves 24 de octubre, 2024

Programar en python el ordenamiento del montón. Mostrar al menos tres ejecuciones con datos de entrada distintos, tal vez revuelto aleatoriamente el arreglo de entrada.

Tarea 4: Problemas de algoritmos aleatorizados
Fecha de entrega: jueves 17 de octubre, 2024

Realice dos codificacion en python para el algoritmo de la contratación de un asistente y el algoritmo de Monte Carlo.

1. ¿Qué tamaño debe tener la lista de candidatos para poder contratar n personas?
2. Debe verificar la estadística de las contrataciones
3. Debe verificar la estadística del algoritmo de Monte Carlo

Tarea 3: Problemas de notación asintótica
Fecha de entrega: martes 1 de octubre, 2024

Resolver estos problemas.

Tarea 2: Tamaño del problema que se puede solucionar
Fecha de entrega: jueves 19 de septiembre, 2024

Resolver este problema.

Tarea 1: Algoritmo para el trazo de una línea en cualquier sentido
Fecha de entrega: jueves 12 de septiembre, 2024

1. Se dede analizar el número de casos que se tienen para trazar una línea. Hacer el diagrama como en clase para visualizar todos los casos.
2. Hacer una tabla de cada caso y la forma de detectarlo
3. Codificar el algoritmo en python
4. Hacer la prueba con este código y realizar la gráfica de salida.
   El código de shell se ejecuta como "bash tarea1.sh"
   La gráfica debe estar hecha con gnuplot.

Última actualización: 15 de noviembre, 2024
Comentarios: fraga en cs cinvestav mx