Estructuras de datos y algoritmos | conjunto 20

Las siguientes preguntas se han hecho en el examen GATE CS 2006.

1. Sean S un problema NP-completo y Q y R otros dos problemas que no se sabe que están en NP. Q es el tiempo polinomial reducible a S y S es el tiempo polinomial reducible a R. ¿Cuál de las siguientes afirmaciones es verdadera?
(A) R es NP-completo
(B) R es NP-duro
(C) Q es NP-completo
(D) Q es NP-duro

Respuesta (B)
(A) Incorrecta porque R no está en NP. Un problema NP Complete tiene que estar tanto en NP como en NP-hard.
(B) Correcto porque un problema NP Completo S es tiempo polinomial educable a R.
(C) Incorrecto porque Q no está en NP.
(D) Incorrecto porque no hay ningún problema NP-completo que sea reducible a Q en tiempo polinomial.

2) Un conjunto X se puede representar mediante una array x[n] de la siguiente manera: considere el siguiente algoritmo en el que x, y y z son arrays booleanas de tamaño n:

algorithm zzz(x[] , y[], z [])
{
   int i;
   for (i=O; i<n; ++i)
     z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i])
}

El conjunto Z calculado por el algoritmo es:
(A) (X Intersección Y)
(B) (X Unión Y)
(C) (XY) Intersección (YX)
(D) (XY) Unión (YX)

Respuesta (D)
La expresión x[i] ^ ~y[i]) da como resultado los únicos 1 en x donde la entrada correspondiente en y es 0. Una array con estos bits establecidos representa el conjunto X – Y
La expresión ~x[i] ^ y[i]) da como resultado los únicos 1 en y donde la entrada correspondiente en x es 0. Una array con estos bits establecidos representa el conjunto Y – X.
El operador «V» da como resultado la unión de los dos conjuntos anteriores.

3. Considere la siguiente recurrencia: ¿Cuál de las siguientes es verdadera? (A) T(n) = Θ(loglogn) (B) T(n) = Θ(logn) (C) T(n) = Θ(raíz cuadrada(n)) (D) T(n) = Θ(n )

Respuesta (B)

  Let n = 2^m
  T(2^m) = T(2^(m/2)) + 1
  Let T(2^m) =  S(m)
  S(m)  = 2S(m/2) + 1  

La expresión anterior es una recursión transversal de un árbol binario cuya complejidad temporal es Θ(m). También puedes probar usando el teorema de Master .

S(m)  = Θ(m)  
      = Θ(logn)  /* Since n = 2^m */

Ahora, volvamos a la función recursiva original T(n)

  T(n)  = T(2^m) = S(m)
                 = Θ(Logn)

Tenga en cuenta que la solución de T(n) = T(√n) + 1 es Θ(Log Log n), la recurrencia anterior es diferente, es T(n) = 2T(√n) + 1

Escriba comentarios si encuentra que alguna de las respuestas/explicaciones es incorrecta, o si desea compartir más información sobre los temas discutidos anteriormente.