Problema 4

Dado un vector desordenado de v[1..n] elementos, demuestra que los siguientes problemas son linealmente equivalentes:

1. Selección: El problema 2.
2. Mediana: Encontrar la mediana en un vector desordenado.
3. Descomposición: Separar v en dos vectores X y Y, tal que para todo elemento x de X y para todo elemento y de Y se cumpla que x <= y.
   

Problema 3

Diseña un algoritmo divide y vencerás lo más eficiente posible que dado un vector n elementos y un k, tenga el siguiente comportamiento:

k= 3 1,2,3,4,5,6

4,5,6,1,2,3

sin utilizar un vector auxiliar

Problema 2

Diseñar un algoritmo que dado un vector desordenado de n elementos y un natural k, encuentre el elemento k-ésimo.

Problema 1

Dado dos vectores ordenados crecientemente con n elementos y dado un natural k, diseñar un algoritmo que encuentre el k-ésimo elemento más pequeño en un tiempo log n.