Si en el ejercicio 3 de la hoja de problemas de divide y vencerás hacemos un pequeño cambio permitiendo hacer variable el número de datos que tienen que sumar una cantidad dada, el problema es sensiblemente más “difícil”: Dado un conjunto S de enteros y un entero x, ¿existe algún subconjunto de S cuya suma sea x? [...]

En la técnica de divide y vencerás, un ejemplar del problema se divide en ejemplares más sencillos del mismo problema que se resuelven separadamente (son ejemplares, de alguna manera, independientes) y sus soluciones se combinan para crear una solución del ejemplar del problema original. En el próximo esquema algorítmico que veremos en clase, programación dinámica, los subproblemas en [...]

. . “A new kind of cipher that would take millions of years to break.” Ese era el título del artículo publicado por Martin Gardner (conocidísimo divulgador científico norteamericano) en la sección Mathematical Games de la revista Scientific American, vol. 237(2), pp. 120-124, en agosto de 1977 (puede descargarse aquí). En él, Gardner describía el método de [...]

Se han publicado en la página de problemas algunos ejercicios del tema que estamos viendo en clase.

. Existe un algoritmo de coste asintótico lineal, en el caso peor, para el cálculo del estadístico de orden k de un vector de tamaño n. Por tanto, en particular, puede usarse para el cálculo de la mediana (haciendo k = techo(n/2) ). Puede verse aquí.

Me habéis preguntado en clase si se conoce algún algoritmo mejor que el de coste cuadrático visto en clase para el problema de la transparencia 84 de algoritmos voraces. He encontrado una respuesta en el libro Computer Algorithms, de Ellis Horowitz, Sartaj Sahni, and Sanguthevar Rajasekaran (Computer Science Press, 1998): It can be reduced from O(n2) [...]