PruebaN°1.

AnalisisyDisenodeAlgoritmos

1. De las siguientes afirmaciones, indicar cuales son verdaderas y cuales son falsas, justifique su afirmación:

a. �� ∈ �(��); Verdadero

b. 2� ∈ �(2); Verdadero

c. �(�) ∈ �(�) ⇒ 2�() ∈ �(2); Falso tomar f(n) = 3n.

d. 3 ∈ �(2); Falso

e. �� �⁄ ∈ �(����); Falso

f. ���� ∈ �(�� �⁄ ) Verdad

g. �� ∈ Ω(��); Verdadero

h. �(�) ∈ Ω(�) ⇒ 2�() ∈ Ω(2); falso tomar f(n) = (1/2)n

i. 3 ∈ Ω(2); Verdadero

j. �� �⁄ ∈ Ω(����) Verdadero

2. Resuelva, sin ocupar el Teorema Maestro, las siguientes ecuaciones de recurrencias y establezca el orden de

magnitud de la solución:

a. �(�) ��

(∑ �(�)

��� ) � ��; con�(0) � 0y� % 0.

b. �(�) � 2�'�� �⁄ ( � log � con� � 2�+; ��2� � 1

3. El algoritmo de ordenación por rastreo de un vector funciona de la siguiente manera: comienza por el principio

del vector y se mueve hacia el final del vector, comparando los pares de elementos adyacentes hasta encontrar

uno que no esté en el orden correcto. Lo intercambia y comienza a moverse hacia el principio, intercambiando

pares hasta encontrar un par en el orden correcto. Entonces se limita a cambiar de dirección y comienza otra vez

hacia el final del vector, buscando un nuevo par fuera de orden. Una vez que alcanza el extremo final del vector,

su misión ha terminado. Implementa (seudo código) dicho algoritmo y calcular su tiempo de ejecución en los

casos mejor, peor y promedio.

4. El siguiente algoritmo denominado “Búsqueda Ternaria” trabaja de la siguiente forma: primero compara con el

elemento en posición n/3 del vector, si éste es menor que el elemento x a buscar entonces compara con el

elemento en posición 2n/3, y si no coincide con x busca recursivamente con el correspondiente subvector de

tamaño 1/3 del original. Verifique que este algoritmo es de tiempo Θ(����). Ayuda: primero escriba un seudo

código, después determine la ecuación de recurrencia y finalmente resuélvala.

5. El problema del “elemento en su posición”. Sea a[1…n] un vector ordenado de enteros todos distintos.

Implementar un algoritmo de complejidad O(logn) en el peor caso capaz de encontrar un índice i tal que 1 ≤ i ≤ n

y a[i] = i, suponiendo que tal índice existe. Utilice la técnica Divide y Vencerás.