1.- Calcule la complejidad tanto de forma analítica como experimental de los siguientes métodos de ordenación: Burbuja, Inserción Directa, Selección Directa, Montículo, Quicksort, Mergesort y método de Shell. Los conjuntos de datos sobre los que se trabajará serán de 1.000, 10.000 y 100.000 elementos enteros. Recopile datos sobre distintas máquinas.

2.- Diseñe un algoritmo “Divide y Vencerás” para multiplicar dos enteros grandes. Debe cuidarse la eficiencia. Calcule la complejidad del algoritmo diseñado.

3.- Disponemos de n cajas distintas, cada una de las cuales tiene un peso P_i y puede soportar una carga encima de ella C_i. Diseñe una heurística voraz que sea capaz de encontrar la disposición de un subconjunto de las n cajas de manera que se apile el mayor número de cajas. Calcule la complejidad del algoritmo.

4.- Juan Gorrilla, el aparcacoches, quiere trabajar menos y cobrar más (como cualquier hijo de vecino). Su trabajo le da la oportunidad de ganar mucho dinero gracias a las propinas que le dan sus “generosos” clientes. El problema es que está harto de tener que mover siempre los coches para poder conseguir aparcar un coche más (y por tanto, ganar una propina más). Juan tiene a su cargo una calle completa (con dos aceras) de L metros para poder aparcar los coches y cuenta con un conjunto de N coches a aparcar.

Diseñe un algoritmo basado en Programación Dinámica que ayude a Juan a encontrar la mejor disposición de los coches utilizando las dos aceras de la calle, sabiendo que cada coche tiene una longitud diferente y cada dueño de coche da una propina distinta, de manera que Juan gane la mayor cantidad de dinero con las propinas aunque no consiga aparcar todos los coches. NOTA: Considere que en la longitud de cada vehículo, ya está incluida la distancia necesaria para poder aparcar el coche.

5.- Darío, “el presi”, ya ha intentado escapar de la cárcel 54 veces, por el laberinto de alcantarillas que pueblan el subsuelo de la prisión. Siempre lo han pillado, pero en la última ocasión casi lo consigue, si no hubiera sido por un gato que maulló cuando no debía. Mañana piensa volver a intentarlo, y esta vez quiere que sea la definitiva. No obstante, los guardias de la prisión piensan poner fin a esta situación y han contaminado el aire de unas cuantas habitaciones del laberinto con un gas somnífero, con el fin de evitar la fuga de Darío. Pero Darío no está dispuesto a quedarse a la sombra más tiempo y ha utilizado sus contactos para conseguir un mapa de las alcantarillas donde están marcadas las salas contaminadas, además, le han informado que podrá soportar la exposición al gas somnífero el tiempo equivalente a atravesar tres salas antes de quedarse dormido como un angelito.

Diseñe un algoritmo utilizando Backtracking que ayude a Darío a encontrar la salida del laberinto por el camino más corto, sin pasar por más de tres salas contaminadas, de manera que la quincuagésima quinta vez sea la vencida y consiga la, tan ansiada, libertad.

6.- Juego. Dominó, DOS jugadores. Se considera el juego del dominó con dos jugadores a los que previamente se les han distribuido todas las fichas. Construya un algoritmo que dada una configuración del juego la evalúe, y devuelva la decisión que produce el resultado indicado.