05. Análisis caso medio

Estudiar el paper "Case-Studies on Average-Case Analysisfor an Elementary Course on Algorithms" de Francesc J. Ferri and Enrique Vidal.

• Luego de obtener los mismos resultados mencione de que se trato la investigación. Casos "Binary Search" y "Palindrome".

• Obtenga las mismas gráficas usando GNUplot (Se recomienda unir java con gnuplot)

• Defina n y T(n) para los casos de prueba.

• Mencione las conclusiones de la investigación.

• Elabore un informe de la experiencia obtenida donde muestre un análisis del paper.

Ejercicio en clase:

Codifique el algoritmo de búsqueda binaria mostrado en el paper en Java. 

Haga simulaciones de 2 hasta 100 datos y mida el promedio del numero de iteraciones del bucle principal. Genere un número aleatorio para la búsqueda. El arreglo tiene que estar ordenado.

Ejemplo de ejecución:

Sea el arreglo a={1 2 3 4 5 6 7 8 } para buscar x=1

left=1, right=8

Iteración 1 (sin condición)            : p=4, 1>4 F, right=3

iteración 2 ~( 4=1 F ó 1>3 F ) V    : p=2, 1>2 F, right=1

iteración 3 ~( 2=1 F ó 1>1 F ) V    : p=1, 1>1 F, right=0 

iteración 4 ~( 1=1 V ó 1>0 V ) F    : No se ingresa al bucle 

p tomo 3 valores: 4, 2 y 1.

En Java

Buscando el elemento 1, 8, 4, 9 y -3 respectivamente:

Entregable

ADALab03_PATERNO_MATERNO.zip

• • Informe.pdf 

  • simulacion1.java (código fuente de la simulación con BinarySearch)

  • simulacion2.java (código fuente de la simulación con Palindrome)

  • BinarySearch.dat (datos obtenidos)

  • Palindrome.dat (datos obtenidos)