Estructuras de datos y algoritmos | conjunto 19

Se han hecho las siguientes preguntas en el examen GATE CS 2009.

1. Sea X un problema que pertenece a la clase NP. Entonces, ¿cuál de las siguientes es VERDADERA?
(A) No existe un algoritmo de tiempo polinomial para X.
(B) Si X se puede resolver de forma determinista en tiempo polinomial, entonces P = NP.
(C) Si X es NP-duro, entonces es NP-completo.
(D) X puede ser indecidible.

La respuesta (C)
(A) es incorrecta porque el conjunto NP incluye tanto P (resolución en tiempo polinomial) como NP-Completo.
(B) es incorrecta porque X puede pertenecer a P (la misma razón que (A))
(C) es correcta porque el conjunto NP-Completo es la intersección de los conjuntos NP y NP-Hard.
(D) es incorrecta porque todos los problemas NP son decidibles en un conjunto finito de operaciones.

2. ¿Cuál es el número de intercambios necesarios para clasificar n elementos utilizando la clasificación por selección, en el peor de los casos?
(A) Θ(n)
(B) Θ(n log n)
(C) Θ(n ² )
(D) Θ(nn ² log n)

Respuesta (A)
Aquí está el algoritmo de clasificación de selección para clasificar en orden ascendente.

   1. Find the minimum value in the list
   2. Swap it with the value in the first position
   3. Repeat the steps above for the remainder of the list (starting at
      the second position and advancing each time)

Como podemos ver en el algoritmo, la ordenación por selección realiza el intercambio solo después de encontrar la posición adecuada del elemento seleccionado actual. Entonces, hay intercambios O (n) realizados en la clasificación por selección.
Debido a que los intercambios requieren escribir en la array, la ordenación por selección es preferible si escribir en la memoria es significativamente más costoso que leer. Este suele ser el caso si los elementos son enormes pero las teclas son pequeñas. Otro ejemplo donde los tiempos de escritura son cruciales es una array almacenada en EEPROM o Flash. No hay otro algoritmo con menos movimiento de datos.

Referencias:
http://en.wikipedia.org/wiki/Selection_sort

3. El tiempo de ejecución de un algoritmo está representado por la siguiente relación de recurrencia:

    if  n <= 3  then   T(n) = n
    else T(n) = T(n/3) + cn

¿Cuál de los siguientes representa la complejidad temporal del algoritmo?
(A) Θ(n)
(B) Θ(n log n)
(C) Θ(n ² )
(D) Θ(n ² log n)

Respuesta (A)

T(n) = cn + T(n/3)
     = cn + cn/3 + T(n/9)
     = cn + cn/3 + cn/9 + T(n/27)
Taking the sum of infinite GP series. The value of T(n) will
be less than this sum.
T(n) <= cn(1/(1-1/3))
     <= 3cn/2

or we can say 
cn <= T(n) <= 3cn/2
Therefore T(n) = Θ(n)

Esto también se puede resolver usando el Teorema Maestro para resolver recurrencias. La expresión dada se encuentra en el Caso 3 del teorema.

4. Las claves 12, 18, 13, 2, 3, 23, 5 y 15 se insertan en una tabla hash inicialmente vacía de longitud 10 usando direccionamiento abierto con función hash h(k) = k mod 10 y sondeo lineal. ¿Cuál es la tabla hash resultante?

Respuesta (C)
Para tener una idea del concepto de direccionamiento abierto, puede consultar las siguientes líneas de Wikipedia
.
El direccionamiento abierto, o hashing cerrado, es un método de resolución de colisiones en las tablas hash. Con este método, una colisión hash se resuelve sondeando o buscando en ubicaciones alternativas en la array (la secuencia de sondeo) hasta que se encuentra el registro de destino o se encuentra una ranura de array no utilizada, lo que indica que no existe tal clave en la array. mesa. Las secuencias de sonda bien conocidas incluyen:

sondeo lineal en el que el intervalo entre sondas es fijo, a menudo en 1.
sondeo cuadrático en el que el intervalo entre sondas aumenta linealmente (por lo tanto, los índices se describen mediante una función cuadrática).
hashing doble en el que el intervalo entre sondeos se fija para cada registro pero se calcula mediante otra función hash.

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.