El blog de Feregrino

A lo largo del semestre, en la materia de Análisis de Algoritmos que llevo con el profesor Edgardo Franco tenemos que realizar varias prácticas. Las prácticas consisten en programar algoritmos conocidos para analizar su comportamiento, tanto en tiempo como en memoria consumida, mientras resuelven problemas de "gran" tamaño.

Muchas (si no es que todas D:) estarán hechas para C, para Linux, esto debido a la librería empleada para medir los tiempos que consume la ejecución del algoritmo. Para facilitar la compilación cada práctica cuenta con un archivo Makefile, el cual contiene todas las instrucciones para compilar y ejecutar las prácticas. Dado que tenemos que analizar los tiempos de ejecución y a veces estos pueden ser muchos, para la ejecución de cada programa redireccionamos la salida estandar para que escribiera directamente a un archivo que podemos manejar sencillamente en una hoja de cálculo. Esto se puede ver en el archivo .sh que acompaña a cada práctica.

Todas las prácticas tienen comentarios, unas más, otras menos, pero los tienen. Aún así si queda alguna duda pues no dudes en preguntar. Otra cosa importante es que estas son solo las propuestas de solución que presentamos, no las copies directamente, basate en ellas o usa porciones del código, eso se vale. El link de descarga está al final del artículo ;).

Con base en el archivo de entrada proporcionado que tiene 200,000 números diferentes. Ordenarlo bajo los siguientes métodos de ordenamiento y comparar experimentalmente las complejidades de estos.

Con base en el ordenamiento obtenido a partir del archivo de entrada de la práctica 01 que tiene 200,000 números diferentes. Realizar la búsqueda de elementos bajo 3 métodos de búsqueda y variantes con procesos ligeros, realizar el análisis teórico y experimental de las complejidades; así como encontrar las cotas de los algoritmos.