ALG 3 QP 07-08 Algoritmos voraces 1. Dado un grafo G, definimos el grado de un v´ertice u ∈ V (G), como el n´ umero de sus vecinos dG (u) = |v ∈ V | (u, v) ∈ A(G)}|. Dado un subconjunto de v´ertices, U ⊆ V (G), el subgrafo inducido per U es el grafo G[U ] = (U, A ∩ U × U ). Definimos el grado de un subconjunto de v´ertices como d(U ) = min dG[U] (u). u∈U Consideramos el problema siguiente: Dados un grafo G = (V, A), y un natural m, decidir si existex U ⊆ V tal que d(U ) m, y en caso de que lo haya obtener un subconjunto U que cumpla la propiedad. Proponed un algoritmo voraz para este problema. Calcula una soluci´on? Por qu´e? Que complejidad tiene? 2. Considerad el problema Max Cut Dado un grafo G = (V, A) queremos obtenir un subconjunt A de v´ertices de V tal que el n´ umero de aristas (u, v) con u ∈ A y v ∈ A es m´aximo. Proponed un algoritmo voraz para el problema MaxCut. Calcula una soluci´on ´optima? Por qu´e? Que complejidad tiene? 4 Backtracking 1. Consideramos el problema: BinPacking (bp) Dado un conjunto de n objetos, y para cada objeto u un tama˜ no s(u) ∈ [0, 1]. Buscar una manera de repartir todos los objetos en contenedores, tal que la suma del tama˜ no de los objetos en cada contenedor no exceda 1, y tal que el n´ umero de contenedores utilizados sea m´ınimo. Los objetos no se pueden fraccionar. Consideramos las siguientes estrategias voraces: First Fit Colocar el siguiente objeto en el primer contenedor en el que se pueda colocar. Best Fit Colocar el siguiente objeto en el contenedor mas lleno en el que cabe el objeto. En caso de que haya m´ as de uno, seleccionar el contenedor con ´ındice menor. First Fit Decreasing Reordenar U , de manera que s(u1 ) s(u2 ) ··· s(un ), aplicar First Fit. ¿Alguno de los algoritmos propuestos resuelve el problema bp?. ¿Qu´e coste tienen? Justifica tu respuesta. Si ninguno de ellos calcula la soluci´on ´optima propon un algoritmo de backtracking para el problema. 2. Dise˜ nad y analizar el coste de un algoritmo de backtracking para resolver los problemas • • • • min-clique min-color set-packing min-bis 5 Programaci´ on din´ amica 1. Consider the problem of storing n books on shelves in a library. The order of the books is fixed by the cataloging system and so cannot be rearranged. Therefore, we can speak of a book bi , where 1 i n, that has a thickness ti and height hi . The length of each bookshelf at this library is L. Suppose all the books have the same height h and the shelves are all separated by a distance of greater than h, so any book fits on any shelf. The greedy algorithm would fill the first shelf with as many books as we can until we get the smallest i such that bi does not fit, and then repeat with subsequent shelves. Show that the greedy algorithm always finds the optimal shelf placement, and analyze its time complexity. 2. This is a generalization of the previous problem. Now consider the case where the height of the books is not constant, but we have the freedom to adjust the height of each shelf to that of the tallest book on the shelf. Thus the cost of a particular layout is the sum of the largest book on each shelf. • Give an example to show that the greedy algorithm of stuffing each shelf as full as possible does not always give the minimum overall height. • Give a dynamic programming algorithm for this problem, and analyze its time complexity. 3. Let P be a pattern string and T a text string over the same alphabet. The edit distance between P and T is the smallest number of changes sufficient to transform a substring of T into P , where the changes may be: • Substitution – two corresponding characters may differ: KAT and CAT. • Insertion – we may add a character to T that is in P : change CT with CAT. • Deletion – we may delete from T a character that is not in P . (a) Compute the edit distance between P = ABCDEFGHIJKL and T = BCDEFFGHIXKL. (b) Design a dynamic programming algorithm to compute the edit distance between a given pattern and text. 4. Let’s assume that we are working with base 2 integers. We start by writing an integer x with n nbits as x1 2n/2 + x0 . In other words x1 are the high order n/2 bits and x0 are the lower order n/2 bits. Similarly we write y as y1 2n/2 + y0 . Thus we have xy = (x1 2n/2 + x0 )(y1 2n/2 + y0 ) = x1 y1 2n + (x1 y0 + x0 y1 )2n/2 + x0 y0 . This equation reduces the problem of computing the product of two n-bit numbers to the problem of computing 4 products of n/2-bit numbers. Design a divide and conquer algorithm for computing the product of two n-bit numbers using the above recurrence and analyze its cost. A second recurrence can be defined as follows. Set p = (x1 + x0 )(y1 + y0 ), then xy = x1 y1 2n + (p − x1 y1 − x0 y0 )2n/2 + x0 y0 . Design a divide and conquer algorithm for computing the product of two n-bit numbers using the above recurrence and analyze its cost. Compare the efficiency of both algorithms.