Ejercicios Entrenamiento

EJERCICIOS DE ENTRENAMIENTO 1. Notación Asintótica -----------------------------------------------------------------------------------------------------------1.1. Analizar si cada una de lassiguientes afirmaciones es verdadera o falsa, argumentando apropiadamente las respuestas dadas:-----------------------------------------------------------------------------------------------------------1.2. En los siguientes ejercicios averigüe si la afirmación es verdadera o no. Sustente su respuesta (para ello construya tablas de valores):

a) b) c) d) e) f) g) h)
Respuestas: a) FA b) VE c) VE d)FA e) VE f) VE g) FA h) FA

------------------------------------------------------------------------------------------------------------

2. Arbol de recurrencias Un ejemplo: T(n) = T(n/3) +T(2n/3) + n. Expanding out the first few levels, the recurrence tree is:

Note that the tree here is not balanced: the longest path is the rightmost one, and its length islog3/2 n. Hence our guess forthe closed form of this recurrence is Θ(n log n).

Otro ejemplo: T(n) = 3T(n/4) + cn2 se asume que n es potencia exacta de 4. como el coeficiente de T(n/4) vale 3, lo expandiremos en 3 ramas:Ejercicios: 2.1. Usando un árbol de recursión como ayuda, encontrar la solución de 2.2. Usando un árbol de recursión como ayuda, encontrar la solución de: T(n) = 2T(n/2) + 1, T(1)= (1) 2.3. Usando unárbol de recursión como ayuda, encontrar la solución de: T(n) = 2T(n/2) + n, T(1)= (1) 3. Método Maestro. Resuelva las siguiente recurrencias usando el método maestro: 3.1. T(n) = 3T(n/2) + n 3.2. T(n)= 7T(n/2) + n 3.3. T(n) = 4T(n/2) + n
2 2 2

T(n) = 3T(n/2) + n

Respuesta: T(n) = Θ(n ) (caso 3). Respuesta: T(n) = Θ (n
lg 7

2

) (caso 1).

Respuesta: T(n) = Θ(n lg n) (caso 2).Respuesta: T(n) = Θ(n Respuesta: T(n) = Θ(n Respuesta: T(n) = Θ(n
1/2

2

3.4. T(n) = 2T(n/4) + lg n 3.5. T(n) = 2T(n/4) + 3.6. T(n) = 2T(n/4) + n

) (caso 1). lg n) (caso 2). ) (caso 3).

n...