8/18/2019 Examen de Análisis de Algoritmos

1/1

Examen de Suficiencia 1-99Análisis y Diseño de Algoritmos

Observaciones:•

Todas las preguntas tienen igual ponderación.• En todas las preguntas debe ser lo más explícito posible.• No se pueden usar apuntes.• Tiempo máximo 2 horas.

1 esuelva las siguiente ecuaciones de recurrencias:

1!1"

22#log!"2!"=

≥+=

T

de potencia ynnnnT nT

2#$# 211$1

2 ===−

−

aaa

aa

n

nn

2 %ado el siguiente con&unto S = {8, 2, 5, 12, 7, 16, 21, 3}, ord'nelo utili(ando losalgoritmos de )eap*ort + ,uic-*ort. %etermine tambi'n el n mero decomparaciones necesarias para /ue el arreglo est' ordenado. %ebe entregar todos los

pasos.0 sando la t'cnica de rogramación %inámica3 constru+a un algoritmo /ue permita

encontrar un árbol binario de b s/ueda óptimo3 para con&untos /ue tienen elementoscon distinta probabilidad de acceso. )aga el análisis de desempe4o del algoritmo.

5 %emuestre /ue3 en el mane&o de clases de e/uivalencias3 si se usa unión ponderada3

entonces todo árbol de altura a lo menos h tiene como mínimo 2h

nodos. " tiliceinducción sobre h!.6 %adas n personas3 nos interesa encontrar una celebridad. na celebridad es una

persona /ue (a) la conocen todos3 + (b) no conoce a nadie "note /ue no puede haber dos celebridades!. Tenemos una matri( C i,j /ue nos dice si i conoce a j. %ise4e unalgoritmo de tiempo O"n! /ue determine /ue no existe celebridad o /ue indi/ue/ui'n es.