CC30A Algoritmos y Estructuras de Datos

Prof. Rodrigo Paredes

Tarea 3

Fecha de entrega: viernes 25 de octubre. No se aceptarán tareas atrasadas.


Objetivos

Uno de los problemas básicos en computación, consiste en dado un conjunto de valores construir un índice que permita realizar búsquedas eficientemente. En esta tarea vamos a comparar el comportamiento de dos estructuras para indexar conjuntos de datos: Árboles de Búsqueda Binaria y Skip Lists. En particular analizaremos el costo de las operaciones de inserción, búsqueda y eliminacion de elementos tanto para los Árboles de Búsqueda Binaria como para las Skip Lists.
 

Descripción de la tarea

La solución trivial para determinar si un elemento pertenece a un conjunto consiste en realizar una búsqueda exhaustiva del elemento dentro del conjunto, lo cual tiene un costo O(n). Si tenemos la oportunidad de preprocesar los datos, podemos construir un índice sobre los datos lo cual nos permite verificar si el elemento pertenece en un tiempo mucho menor. En esta tarea vamos a comparar dos índices: Árboles de Búsqueda Binaria (ABB) v/s Skip Lists (SL).

Sabemos que ambos índices realizan las operaciones de inserción, borrado y búsqueda en tiempo promedio O(log n), la pregunta que naturalmente surge es: ¿cuál índice es mejor?. Para ello vamos a hacer experimentos de inserción, búsqueda y borrado utilizando ambas estructuras, y vamos a medir el costo de las operaciones de interés (inserciones, búsquedas y borrados) contando las comparaciones de llaves que sean necesarias. Luego de tener las comparaciones podemos construir un modelo de ajuste para cada operación de interés, y comparando los modelos obtenidos para cada operación, podremos determinar que índice es mejor bajo las condiciones del estudio.

Esta tarea se divide en dos partes:

  1. Implementación de los índices de búsqueda: ABB y SL.
  2. Medición experimental de los tiempos para inserción, borrado y búsqueda. Para medir los tiempo deben contar las comparaciones de llaves.

Pruebas

Se les proporciona un archivo que contiene una permutación aleatoria compuesta por números entre 1 y 150000.

Vamos a trabajar con valores de n = 1000, ..., 100000. Para cada valor de n se realizará la carga de los datos, una serie de búsquedas (que pueden ser exitosas o no) y luego eliminar los n valores del índice.

Consideren 2 rangos para valores de n, el primer rango es n = 1000, 2000, 3000, ..., 10000 elementos y el segundo n = 10000, 20000, 30000, ..., 100000 elementos.

Para cada valor de n realice el experimento de:

  1. Insertar n valores en cada uno de los índices (ABB o SL). Para esta parte inserte los primeros  n valores del archivo de datos a cada uno de los índices.
  2. Buscar n valores. En esta parte realice n búsquedas tanto para valores que pertenecen a los elementos indexados (búsquedas exitosas) como para valores que no pertencen a los elementos indexados (búsqueda infructuosa). Considere 2/3 de búsquedas exitosas y 1/3 de búsquedas infructuosas.
  3. Eliminar n valores. En esta parte elimine los primeros n  valores de cada uno de los índices (ABB o SL)
Para cada experimento realizado, se deben medir las comparaciones realizadas para cada valor de n.

Por último obtenga los modelos de inserción, búsqueda y borrado, recuerde que cada inserción, búsqueda o borrado tiene costo promedio O(log n) por operación, por otro lado hacer n operaciones de inserción, borrado o búsqueda tiene costo promedio O(n log n).

Hints

Dado que sabemos que ambas extructuras tienen el mismo orden en tiempo promedio, para determinar que índice es mejor es necesario comparar las constantes.
 

Restricciones

Hints

Tiene que implementar tanto el árbol de búsqueda binaria como la skip list, ponga especial cuidado en los métodos: Junto con estos métodos, implemente todo lo demás que considere necesario (borrado de elementos, destructores, métodos para consultar si la lista esta vacia, etc.)

Ponderación

El informe equivale a un 50% de la nota de tarea.
El código equivale a un 50% de la nota de tarea.

Entrega de la tarea

 
La entrega de la tarea debe incluir un informe escrito donde se describa y documente el programa realizado, y se incluyan ejemplos de entradas y salidas.

El informe debe ser entregado en la Secretaría Docente de Computación (donde Magaly, tercer piso Edificio de Computación, hasta las 17:00 horas del último día de plazo), y el código fuente (junto a un archivo README que explique como compilar) debe ser enviado utilizando el Cursomático de cc30a.

El contenido del informe debe seguir la siguiente pauta común para todas las tareas:
 

  • Portada