Div y Conquista: Contando Inversiones, Puntos en el Plano, Karatsuba & Puntos Extremos en Polígonos

Question 1

Explique el Problema de Contar Inversiones

Answer 1

Sean:

• Un conjunto de n elementos
• Dos listas ordenadas de los n elementos

Queremos tener una medida de semejanza / diferencia entre las dos listas.

Question 2

Contar Inversiones: Explique el concepto de Diferencias entre las Preferencias

Answer 2

Llamaremos A y B a las listas de preferencias.

Utilizaremos el orden de aparición de los elementos de A para identificar las diferencias: 1, 2, ... , n.

Por otro lado estará B, que posiblemente estará “fuera de órden”: 2, 1, 5, ... , n.

Si B está en orden, se dice que representa el mismo orden de preferencia que A.

Question 3

Explique qué se quiere saber en el problema de Contar Inversiones

Answer 3

Queremos saber qué tan lejos está B de estar ordenada de forma ascendente.

Si bi < b(i + 1) para todo i, entonces A = B.

Question 4

Contar Inversiones: ¿En qué condiciones dos elementos están invertidos?

Answer 4

Dos elementos bi, bj con i < j están invertidos si bi > bj.

Question 5

Contar Inversiones: ¿Qué complejidad tiene calcular la cantidad de inversiones con fuerza bruta?

Answer 5

Con fuerza bruta, calcular la cantidad de inversiones es O(n^2), porque se compara cada posición con todas las siguientes.

Question 6

Contar Inversiones: ¿Cuál es la forma óptima de contar la cantidad de inversiones entre A y B?

Answer 6

La forma óptima es usando un merge sort, que alamacena la cantidad de inversiones necesarias para ordenar la lista B.

Question 7

Explique el pseudocódigo para contar inversiones con Merge Sort

Answer 7

El código tiene dos partes:

1. ordenar_contar
2. merge_contar
3. Para la función de ordenar_contar, tenemos:

a. Sea L el arreglo con los elementos de B
b. L1 = primer mitad del arreglo L a procesar
c. L2 = segunda mitad del arreglo L a procesar
d. Llamar a la función `ordenar_contar` para L1. Devuelve r1 (#inversiones) y L1_ord, L1 ordenado.
e. Llamar a la función `ordenar_contar` para L2. Devuelve r2 (#inversiones) y L2_ord, L2 ordenado.
f. Llamar a la función `merge_contar` para L1_ord y L2_ord. Devuelve r (#inv) y L (ordenado).
g. Devolver (r1+r2+r, L)

2. Para la función de merge_contar, tenemos:

a. Un contador de inversiones y L una lista vacía
b. Dos contadores i  y  j de posición para la lista A y B
c. Mientras i < |A|  y  j < |B|:
             a = A en posición i
             b = B en posición j

             Si a > b:
                          Guardar elemento a en la posición i+j de L
                          i ++

             De lo contrario:
                          Guardar el elemento b en la posición i+j
                          j++
                          inversiones += |A| - i

d. Para los elementos entre i y |A| - 1: agregarlos a L[i+j] e inversiones +=|B|.

e. Para los elementos entre j y |B| - 1: agregarlos a L[i+j].

f. Retornar la cantidad de inversiones y la lista L

Question 8

¿Qué complejidad tiene Contar Inversiones con Merge Sort?

Answer 8

Cada problema de n elementos se deivide en 2 subproblemas de n/2 elementos.

• La unión de los resultados se construye recorriendo los n elementos => O(n).

=> La relación de recurrencia es:
T(n) = 2 T(n/2) + O(n)
Usando el teorema maestro, nos queda T(n) = O(n logn)

Question 9

Explique el problema de Puntos Más Cercanos en el Plano

Answer 9

Sean:

• P un conjunto de ´n´ puntos en el plano
• d(p1,p2) la función distancia entre p1 y p2.
• Queremos encontrar los puntos más cercanos en P.

Question 10

Puntos Más Cercanos en el Plano: ¿Cuál es la complejidad por fuerza bruta?

Answer 10

Si quisiéramos solucionar esto por fuerza bruta, calcularíamos la distancia entre cada punto y el resto de ellos, y nos quedaríamos con los dos de menor distancia.

Teniendo n puntos, la complejidad es O(n^2).

Question 11

Puntos Más Cercanos en el Plano: ¿Cuáles son los preliminares a tener en cuenta?

Answer 11

Asumiremos:

• No existen puntos repetidos o que compartan coordenadas en x o y. Cada apunto es único.
• Existe Px, que almacena los puntos ordenados de acuerdo a la coordenada x; y Py, para hacer lo mismo con respecto a la coordenada y.

Question 12

Puntos Más Cercanos en el Plano: Explique la división en subproblemas.

Answer 12

Vamos a llamar Q al set de puntos que se encuentran en la mitad izquierda del eje x, y R al set de puntos que se encuentran en la mitad derecha.

• Para cada Q, calcularemos Qx y Qy.
• Para cada R, calcularemos Rx y Ry.
• Para cada punto q en Q y r en R, almacenaremos en qué posición aparece en Qx, Qy y Rx, Ry.

Esto podemos hacerlo en O(n) usando P, Px y Py.

Question 13

Puntos Más Cercanos en el Plano: ¿Cómo se resuelve de forma recursiva? ¿Cuál es la complejidad? ¿Qué posible problema existe?

Answer 13

El problema base es un set de 2 o 3 puntos.

• Vamos a subdividir los problemas en 2 partes.
• Vamos a juntar los problemas comparando los pares de puntos retornados por cada subproblema, y quedándonos con el que tenga menor distancia.

La complejidad es de O(n logn).

Un posible problema es que la distancia mínima podría darse entre dos puntos de distintos espacios. Para esto debemos comparar los puntos de un lado con los del otro, lo cual nos da una complejidad de O(n^2), que es igual que la complejidad en fuerza bruta.

Question 14

Puntos Más Cercanos en el Plano: Explique la Solución Eficiente con División y Conquista

Answer 14

Siendo n la cantidad de elementos, creamos Q con puntos de P de 1 hasta n/2 y R con puntos de P desde n/2 a n

1. Llamamos x* a la coordenada más a la derecha en Q.
2. Llamamos L a la línea vertical en x*, tal que L separa a Q de R.
3. Vemos que si la distancia mínima está entre un punto entre Q y R, entonces tiene que ser menor a δ.

δ = min (δq, δr). Ambos δq y δr son la distancia más chica entre dos puntos, en cada parte Q y R.

4. Nos interesa conocer qué puntos S están a una distancia menor a δ de L. Podemos obtenerlos recorriendo P en O(n).
5. Subdividimos el espacio en celdas de δ/2 x δ/2, tal que sólo puede existir un punto o ninguno en cada celda.
6. Como cada punto de S está en una celda, podemos comparar cada punto únicamente con otros puntos de S que estén en celdas cercanas. Recorriendo de menor a mayor en orden del eje y, comparo únicamente con las celdas que están hasta 3 filas más arriba que la actual (15 celdas en total).
   Este proceso es O(n), en vez de ser un O(n^2).
7. Una vez que obtenemos el par de puntos del conjunto S que está a menor distancia, comparamos con δ:
   a. Si es menor, devolvemos ese par de puntos.
   b. Si no, devolvemos el mínimo entre δq y δr.
8. Se sigue de forma recursiva hasta que se alcanza el nivel más alto y se devuelve el par de puntos con menor δ para todo el plano.

Question 15

Karatsuba: Explique el problema

Answer 15

Sean X e Y números enteros de n bits cada uno, queremos calcular su multiplicación. La idea es mejorar la complejidad con el método tradicional (multiplicación bit a bit), que es O(n^2).

Question 16

Karatsuba: ¿Cómo se mejora la complejidad?

Answer 16

La idea es dividir los bits en 2 partes. Se representan de la siguiente forma:

X = x1 * 2^(n/2) + x0
Y = y1 * 2 ^(n/2) + y0

De esta forma, al querer operar X * Y, nos queda la distributiva de ambos:

(x1 * 2^(n/2) + x0) * (y1 * 2^(n/2) + y0)
= x1.y1 * 2^n + (x0.y1+x1.y0) * 2^(n/2) + x0.y0

Esta multiplicación se puede realizar recursivamente hasta que sea de 1 a 1 bits.
Además, todos los x*y que ya calculé puedo guardarlos, no hace falta volver a calcularlos. Por lo que como hay cálculos que nos ahorramos, la relación de recurrencia es:

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

Que es O(n^1.59), aunque el algoritmo terminó evolucionando y su complejidad llegó a probarse poder ser O(n logn).

Question 17

Puntos Extremos en polígonos: Explique el problema

Answer 17

Sea un polígono de n vértices V = (v0, ..., vn) con vn = v0 en orden contrareloj, queremos determinar el vértice extremo (mayor o menor) a un eje u.

Question 18

Puntos Extremos en polígonos: Explicar la solución por fuerza bruta y su complejidad

Answer 18

• Se realiza una proyección ortogonal a una recta u.
• Se verifica si es mayor al mayor de los anteriores.
  ò
• Se verifica si es menor al menor de los anteriores.

La complejidad es O(n).

Question 19

Puntos Extremos en polígonos: ¿Se puede mejorar la complejidad de fuerza bruta?

Answer 19

Se puede, pero sólo si el polígono es convexo. Es decir, si sus ángulos miden como mucho 180 grados. Además, cualquier línea perpendicular L debe cortar como máximo 2 veces al polígono (tiene que ser más bien “redondito” digamos)

Question 20

Puntos Extremos en polígonos: Explique la nomenclatura de los vértices

Answer 20

• ei es el iésimo segmento del vértice vi a vi+1.
• eVi es el vector que va de Vi a Vi+1

Si eVi mira para arriba en la proyección, es positivo. Si mira para abajo, es negativo.

Question 21

Puntos Extremos en polígonos: Explique la idea general del problema.

Answer 21

Supongamos que sabemos que el vértice máximo se encuentra en el polígono entre los vértices a y b.

Elegimos un vértice c entre a y b.
Creamos dos líneas poligonales: una [a, c] y otra [c, b]. El máximo tiene que estar en alguno de los dos segmentos.

Analizamos el vector Va y Vc:

Para Va+

• Si Va+ y Vc -, me quedo con el tramo [a, c]
• Si Va+ y Vc+, con c arriba de a: [c, b]
• Si Va+ y Vc+, con a arriba de c: [a,c]

Para Va-

• Si Va- y Vc+, me quedo con el tramo [c,b]
• Si Va- y Vc-, con c arriba de a: [a,c]
• Si Va- y Vc-, con a arriba de c: [c, b]

Question 22

Puntos Extremos en polígonos: Explique la solución y su complejidad.

Answer 22

Iteramos dividiendo el problema en 2 líneas poligonales.

• En el caso de que nos queden 3, comparamos 1:1 y obtenemos el máximo.
• De lo contrario, determinamos cuál de los casos de Va y Vc aplica.
• Finalmente, se actualizan a, b, y c según corresponda.

Complejidad:
- Reducimos a la mitad la cantidad de vértices
- Convertimos cada uno en un nuevo subproblema (1 llamada recursiva)
- Realizamos operaciones O(1).

=> La relación de recurrencia es:
T(n) = 1 * T(n/2) + c

Por lo que la complejidad nos queda: O(logn), por el teorema maestro.

Question 23

Resuelva:

El orden de un listado en el ranking actual es:
[ A, 3 | B, 4 | C, 2 | D, 8 | E, 6 | F, 5 ]

a. ¿Cómo se puede resolver por fuerza bruta? Analizar complejidad temporal / espacial
b. Proponer una solución, usando división y conquista.
c. Dar el pseudocódigo para el punto b.
d. Realice el análisis de la complejidad temporal por el teorema maestro.
e. Realice el análisis de la complejidad temporal desarrollando la recurrencia.
f. ¿Cuál es la complejidad espacial?

Answer 23

a. Para cada elemento, se recorre comparando con los posteriores. Si la posición del elemento es menor a la del actual, se suma 1 a las inversiones. La complejidad es O(n^2) y la espacial es O(n).

b. Se puede utilizar Mergesort, con un contador para inversiones.

Ordenar-Contar(L):
	
	Si |L|=1
		Retornar (0,L) // No hay inversiones
	Sino
		Sea A los techo(n/2) primeros elementos de L
		Sea B los piso(n/2) restantes elementos de L
		(ra,A) = Ordenar-Contar(A)
		(rb,B) = Ordenar-Contar(B)
		(r,L) = Merge-Contar(A,B)
	
	Retornar (r+ra+rb,L)

-----

Merge-Contar(A,B)
	Sea L lista
	inv = 0
	i = 0, j = 0 // posición en la lista A y B

	Mientras i < |A| y j < |B|:
		a = A[i], b = B[j]
		Si a > b
			L[i+j] = a , i++
		Sino
			L[i+j] = b , j++
			inv =+ (|A|- i)
	
	Desde i hasta |A|-1:
		L[i+j] = A[i]
		inv += |B|

	Desde j hasta |B|-1
		L[i+j] = B[i]

	Retornar (inv,L)

d. Solución: Θ(n logn)

e. Cada nivel consume cn operaciones. Tenemos logn niveles, por lo que se divide el problema una log2n cantidad de veces para pasar de n a 1.
El tiempo total es de cn . logn, por lo que la complejidad es O(n logn).

f. O(n) para guardar los n elementos.

Question 24

Puntos más cercanos en el plano: Resuelva

p1 = 1, 4
p2 = 2, 8
p3 = 4, 9
p4 = 3, 3
p5 = 6, 10
p6 = 5, 6
p7 = 8, 2
p8 = 9, 7
p9 = 7, 1
p10 = 10, 5

Answer 24

d_min = p9, p7
δmin = 1.41

Question 25

Resuelva

Se cuenta con un vector de n posiciones en el que se encuentran algunos de los primeros “m” números naturales, ordenados en forma creciente (m >= n).
En el vector no hay números repetidos.

Se desea obtener el menor número no incluído.

Ejemplo:
[ 1, 2, 5, 10]

a. Explicar la complejidad por fuerza bruta.
b. Proponer una solución por div y conquista, y explicar la complejidad por división y conquista. Dar el pseudocódigo.
c. Resolver para [1, 2, 3, 4, 5, 8, 10]

Answer 25

a. Por fuerza bruta, es O(n) temporal y O(n) espacial.

b. Propuesta:

Funcion encontrar_faltante

Parámetros iniciales:
array = A
índice = 0

1. dividir el array en A1 y A2. El último elemento de A1 se llama `Am`.

2. Comparar `m` y `m+1` contra `Am` y `Am+1`.

3. Si `m != Am`, devolver `encontrar_faltante(A1, index)`

4. Si `m+1 != Am+1`, devolver m+1

5. De lo contrario, devolver `encontrar_faltante(A2,m)`

c. 3 iteraciones:
[1, 2, 3, 4, 5, 8, 10]
[5, 8, 10]
[5, 8] => faltante: 6

Question 26

Puntos Extremos en Polígonos:

Encontrar el punto extremo máximo y mínimo para el polígono formado por los siguientes vértices:

x, y:
1,2
2,3
3, 3.5
4, 3
4, 1
3, 0
1.5, 0.5

Answer 26

Máximo: 3, 3.5
Minimo: 3, 0