Departamento de Cs.

e Ingenierı́a de la Computación
Universidad Nacional del Sur

Algoritmos y Complejidad
Trabajo Práctico 3
Algoritmos Dividir y Conquistar
primer semestre de 2023

1. Resolver las siguientes recurrencias e indicar el orden de t(n).

(a) t(n) = 3t(n − 1) − 2t(n − 2), sujeta a t(0) = 0, t(1) = 1.

(b) t(n) = 4t(n − 1) − 4t(n − 2), sujeta a t(0) = 1, t(1) = 4.
(c) t(n) = t(n − 2).
(d) t(n) = 4t(n − 1) + 2n , sujeta a t(0) = 0, t(1) = 2.
(e) t(n) = t(n − 1) + n.

En los incisos (a), (b) y (d) determinar las constantes en la solución general.

2. Considere la recurrencia t(n) = 4t(n − 1) − 2n . Determinar el orden asintótico exacto de la

función cuando:

ˆ t(0) = 1
ˆ t(0) = 2

¿Son del mismo orden? ¿Por qué?

3. Demostrar que nk es suave para todo k ∈ N.

4. Mostrar que las funciones nlog n , 2n , y n! no son suaves. (Ayuda: probar que no son b-suaves
para b=2).

5. Efectuar los cambios de variable necesarios y resolver las siguientes recurrencias, indicando el
orden condicional exacto en el que está t(n). Verificar si es posible aplicar la Regla de Suavidad.

(a) t(n) = 4t(n/2) + n.

(b) t(n) = 4t(n/2) + n2 .
(c) t(n) = 2t(n/2) + lg n.
(d) t(n) = 2t(n/2) + n lg n.
√ k
(e) t(n) = 2t( n) + lg n (para n de la forma 2(2 ) ).

6. Teorema Maestro [CLRS09, Sección 4.5]

(a) Indicar qué recurrencias del ejercicio 5 pueden resolverse utilizando el método del Teorema
Maestro. Resolver dichas recurrencias utilizando ese método.
(b) Resuelva las siguientes recurrencias utilizando el Teorema Maestro.
ˆ t(n) = 3t(n/2) + n2
ˆ t(n) = 16t(n/4) + n.
ˆ t(n) = 3t(n/3) + n/2.
 7. Existe una generalización del método de la ecuación caracterı́stica que permite resolver recurrencias
de la forma

t(n) = a1 t(n − 1) + a1 t(n − 2) + . . . + ak t(n − k) + bn1 p1 (n) + bn2 p2 (n) + . . .

donde los bi son constantes y los pi son polinomios en n de grado si . La ecuación caracterı́stica
para estas recurrencias se construye de la siguiente manera:

(xk − a1 xk−1 − . . . − ak )(x − b1 )s1 +1 (x − b2 )s2 +1 . . . = 0

Utilizando la generalización del método de la ecuación caracterı́stica, resolver las recurrencias

que se enuncian a continuación. Determinar el valor de las constantes en la solución general.

(a) t(n) = 2t(n − 1) + n + 2n , sujeta a t(0) = 0.

(b) t(n) = 4t(n − 1) − 4t(n − 2) + 3n + n2 .
(c) t(n) = 4t(n − 1) − 2n , sujeta a t(0) = 1.
(d) t(n) = 3t(n − 1) − 2t(n − 2) + 3(2n−2 ), sujeta a t(0) = 1 y t(1) = 2.

8. Para la implementación recursiva de la operación de búsqueda en un Árbol Binario de Búsqueda,

enunciar y resolver la recurrencia generada por su tiempo de ejecución en el peor caso.

9. Considere el problema de encontrar el mı́nimo y el máximo elemento de un arreglo de n elementos.

Dar un (único) algoritmo Dividir y Conquistar que resuelva este problema y analice el tiempo
de ejecución.

10. Plantear y resolver las recurrencias del tiempo de ejecución de QuickSort para:

ˆ Peor caso.
ˆ Mejor caso.

11. Considerar la variante del algoritmo de mergesort que en lugar de dividir el arreglo en dos
mitades lo separa en tres partes de tamaños ⌊n/3⌋, ⌊(n + 1)/3⌋ y ⌊(n + 2)/3⌋, que son ordenadas
recursivamente y luego mezcladas para obtener la solución final. Escribir el pseudocódigo y
realizar un análisis del orden del tiempo de ejecución de este algoritmo.

12. Adaptar el algoritmo de MergeSort para que reciba un arreglo de números A[1 . . . N ] y retorne
un nuevo arreglo con los elementos de A ordenados y sin duplicados. Por ejemplo, para A =
[1, 7, 12, 3, 22, 12, 7, 12] la salida deberı́a ser [1, 3, 7, 12, 22].

13. Multiplicacion de enteros largos [BB96, Sección 7.1]

Sean u y v enteros de exactamente m y n dı́gitos respectivamente, con m ≤ n. El algoritmo
clásico de multiplicación obtiene u × v con un tiempo de ejecución en O(nm). El algoritmo de
dividir y conquistar desarrollado en teorı́a considera que ambos números son del mismo tamaño,
aún cuando m es mucho mas pequeño que n; esto provoca que el orden del tiempo ejecución del
algoritmo sea O(nlog 3 ).
Reformular este algoritmo de modo que se aproveche la diferencia de tamaño para lograr un
tiempo de ejecución en O(nmlog(3/2) ).

14. Dado un arreglo de enteros no necesariamente positivos A[1 . . . N ], se desea hallar el subarreglo
A[i . . . j] cuya suma sea máxima. Es decir, se desea hallar un par de ı́ndices 1 ≤ i ≤ j ≤ N tal
que la suma A[i] + A[i + 1] + . . . + A[j] sea la máxima posible.
Por ejemplo, para el arreglo A = [3, −4, 5, −2, −2, 6, −3, 5, −3, 2], el subarreglo de suma máxima
es [5, −2, −2, 6, −3, 5] cuya suma es 9.
 (a) Escribir el pseudocódigo de un algoritmo que resuelva el problema. El algoritmo deberá
resolver una instancia de tamaño N a partir de 2 instancias de tamaño N2 y el orden del
tiempo de ejecución de la etapa de combinación deberá ser O(N ).
(b) Realizar el análisis del tiempo de ejecución a partir de una recurrencia y el Teorema Maestro.
15. Dado un arreglo ordenado A[1 . . . N ] de enteros distintos, algunos de los cuales pueden ser
negativos. Dar un algoritmo que encuentre un ı́ndice i tal que A[i] = i ó detecte que no existe
tal ı́ndice. El tiempo de ejecución debe estar en el orden de O(log n) en el peor caso.
16. Par de puntos más cercanos [CLRS09, Seccion 33.5]
(a) ¿Cuál es la máxima cantidad de puntos que entran en un cuadrado de d × d si la distancia
entre cada par de puntos es al menos d?
(b) En la etapa de combinación del algoritmo que resuelve este problema, se recorren todos los
puntos dentro de Franja y se chequea la distancia con otros 7 puntos. Justificar por qué
son suficientes 7 puntos.
(c) Determine el orden del tiempo de ejecución de la etapa de combinación y del algoritmo
completo cuando:
ˆ Se ordenan los puntos por coordenada y en cada etapa de combinación.
ˆ Se recibe como parámetro la lista de puntos ordenados por coordenada y.
17. Exponenciación modular [BB96, Sección 7.7]
(a) Sea N (n) la función que indica la cantidad de multiplicaciones realizadas por el algoritmo
de exponenciación modular para calcular an . Defina N (n) como una recurrencia.
(b) Analizar cuántas multiplicaciones realiza el algoritmo de exponenciación modular para
calcular a15 y a16 .
(c) Mostrar que N (n) NO es eventualmente no decreciente.
(d) Mostrar que N (n) está en el orden Θ(log n).
18. Sea T un arreglo de n elementos. Un elemento x se dice mayoritario si el número de elementos
de T iguales a x es mayor que n/2. Escribir un algoritmo para encontrar el elemento mayoritario
de un arreglo (si es que existe), cuyo tiempo de ejecución sea O(n log n).
19. Dibujando el horizonte
Se desea desarrollar un algoritmo para asistir en la tarea de dibujar en 2 dimensiones el horizonte
de una ciudad dados los datos de altura y ubicación de sus edificios. En esta ciudad todos los
edificios tienen contornos rectangulares y están construidos sobre un terreno alineado y nivelado.
Cada edificio se representa como una tupla de 3 valores (Ii , Hi , Di ) donde Ii y Di son los extremos
izquierdo y derecho respectivamente del edificio i y Hi es la altura de dicho edificio. Todos los
valores Ii , Hi , Di son enteros positivos.
 Por ejemplo dados los edificios (5, 7, 10) (8, 18, 12) (11, 16, 14) (13, 10, 18) (16, 23, 21) (20, 8, 23)
(22, 4, 25) (25, 2, 30) (30, 12, 36) (41, 11, 46) (44, 6, 50), estos se ubican en la ciudad como se ve
en la figura 1. El horizonte a obtener para esta ciudad es el que se muestra en la figura 2. La
representación utilizada para un horizonte es una secuencia de valores (v1 , v2 , v3 , ..., vn−1 , vn ) en
la que los vi tales que i es impar representan lineas verticales del horizonte (extremos de edificios)
y los vi tales que i es par representan lineas horizontales (alturas de los edificios).

Para el ejemplo de horizonte de la figura 2 la secuencia del horizonte es la siguiente:

(5, 7, 8, 18, 12, 16, 14, 10, 16, 23, 21, 8, 23, 4, 25, 2, 30, 12, 36, 0, 41, 11, 46, 6, 50, 0)
La secuencia del horizonte puede ser vista como el camino que se realiza para hacer el dibujo
sin levantar el lapiz comenzando en el mı́nimo punto de las coordenadas x y moviendose vertical
y horizontalmente por el contorno hasta el final. De esta manera en cada posición de las
coordenadas x en las que no haya un edificio, incluyendo al final del horizonte, el valor que
representa esa situación en la secuencia es el 0.

(a) Desarrolle un algoritmo que dada la lista de tuplas de los edificios construya la secuencia
del horizonte como se describe en este enunciado utilizando la técnica Dividir y Conquistar.
Diseñe para esto un algoritmo que a partir de dos horizontes de una misma ciudad H1 y
H2 construya el horizonte resultante para la ciudad completa.
Por ejemplo: la mezcla de los horizontes (1, 4, 6, 8, 10, 2, 13) y (8, 5, 11, 9, 12) es el horizonte
(1, 4, 6, 8, 10, 5, 11, 9, 12, 2, 13).
Identifique en su resolución: cuáles son los subproblemas, cómo los obtiene a partir del
problema original y cómo obtiene finalmente la solución general (combinación de soluciones
a subproblemas).
Si hace uso de primitivas muestre su implementación en pseudocódigo o explique detalladamente
qué realiza cada una.
(b) Analice cuál es el orden del tiempo de ejecución de su algoritmo. Muestre la recurrencia y
explique cómo la resuelve.

?refname?
[BB96] Gilles Brassard and Paul Bratley. Fundamentals of Algorithmics. Prentice Hall, 1996.

[CLRS09] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction
To Algorithms. The MIT Press, 3rd edition, 2009.