UEA: Diseño de Algoritmos
Trimestre: 2007 Invierno
Entrega: 14 de febrero de 2007 a las 10pm

Problema 1: Diseñe un algoritmo usando la técnica de divide y vencerás para resolver el problema de selección descrito en el examen. Escriba un programa llamado seleccion basado en su algoritmo que acepte como entrada dos enteros positivos N y K y un vector de N enteros con componentes A[0], A[1], ..., A[N-1] y que escriba como salida el vector A reorganizado de modo que A[0], ..., A[K-1] sean menores o iguales que A[K] y además A[K+1], ..., A[N-1] sean todos mayores o iguales que A[K] (es decir, A[K] contiene al (K+1)-ésimo elemento más pequeño). Puede suponer que 0 <= K < N <= 1,000,000.

Problema 2: Diseñe un algoritmo usando la técnica de búsqueda con retroceso para resolver el siguiente problema: Dados dos enteros positivos N y K encuentre la cantidad F de formas distintas en que se puede escribir N como suma de K enteros positivos. Considere que dos formas son idénticas si sólo difieren en el orden de sus sumandos. Por ejemplo, si N = 7 y K = 3 entonces F = 4 debido a que 7 = 1 + 1 + 5 = 1 + 2 + 4 = 1 + 3 + 3 = 2 + 2 + 3. Escriba un programa llamado ksuma basado en su algoritmo que acepte como entrada dos enteros positivos N y K y que escriba como sallida el número F. De nuevo, si la entrada fuera 7 3 entonces la salida debe de ser 4. Puede suponer que 1 <= K <= N <= 100.