Universidad Andres Bello

Facultad de Ingeniera

Ingeniera en Computacion e Informatica

Diseno de Algoritmos

Gua Solemne 1Prof. Catedra: Carlos Contreras Bolton Fecha: 14 de Abril de 2015Profs. Laboratorio: Tamara Saez Felipe Reyes

Ejercicio 1Realice los siguientes dos puntos:

1. Ordene las siguientes funciones en orden O(): n log n,n, log log n, 1/n, n/ log n.

2. Resuelva las siguientes recurrencias:

T (n) = 3T (n 1) + 2, T (1) = 1. (solucion (3n))T (n) = 4T (n/2) + n2. (solucion (log n n2))T (n) = 4T (n/2) + n2

n. Resuelva por el metodo del teorema maestro. (solucion (n3))

T (n) = 8T (n/2) + n2. Resuelva por medio del metodo de la substitucion. (solucion (n3))

T (n) = 2T (n/2) + 3n+ 2 si n 2 y potencia de 2, T (1) = 4. (solucion: (n log n))

Ejercicio 2Resuelva la siguiente recurrencia, (solucion (2n)):

T (n) =

{1 n = 1n1

i=1 T (i) + n2 n 2

Ejercicio 3Resuelva las siguientes recurrencias:

T (n) = 5T (n 1) 6T (n 2), T (0) = 1, T (1) = 2. (solucion (2n))T (n) = 5T (n 1) 6T (n 2), T (0) = 0, T (1) = 2. (solucion (3n))

Ejercicio 4Para resolver cierto problema se dispone de un algoritmo trivial cuyo tiempo de ejecucion t(n), paraproblemas de tamano n, es cuadratico (i.e. t(n) (n2). Se ha encontrado una estrategia Divide yConquista para resolver el mismo problema; dicha estrategia realiza D(n) = n log n operaciones paradividir el problema en dos subproblemas de tamano mitad y C(n) = nlogn operaciones para componeruna solucion del original con la solucion de dichos subproblemas. Es la estrategia Divide y Conquistamas eficiente que la empleada en el algoritmo trivial?. Demuestre.

Ejercicio 5El algoritmo de Prim y de Kruskal funciona si hay aristas negativas? Justifique su respuesta.

Ejercicio 6Demuestre porque el algoritmo de Dijsktra no funciona bien si las aristas tienen costos negativos. Justi-fique su respuesta con un argumento o un contraejemplo.

Diseno de Algoritmos Gua Solemne 1

Ejercicio 7Disene un algoritmo para encontrar todos los componentes conexo de un grafo. Si G tiene K componen-tes conexas, cuantas operaciones BUSCAR-CONJUNTO se realizan? Cuantas operaciones UNION serealizan? Expresese el resultado en terminos de |VERTICES|, |ARISTAS| y K.

Carlos Contreras Bolton2