Análisis y Diseño de Algoritmos

EXAMEN 3 – 2021B

Universidad Nacional de San Agustín Departamento de Ingeniería de Sistemas

Curso:        Análisis y Diseño de Algoritmos                Grupo:        B        NOTA: Apellidos y Nombres:   ORDOÑEZ CCORICCAZA JUAN CARLOS                 Profa. Dra. Aurea Soriano-Vargas[pic 1]

1. Esta prueba contiene 8 páginas y 5 preguntas.
2. Por favor, coloque todos los pasos en las preguntas. Respuestas sin todos los cálculos no recibirán crédito.
3. El total de puntos de esta evaluación es 20.
4. El tiempo estimado es de 60 minutos.
5. Al terminar el examen, escanear o tomar foto y enviar por google classroom.

[pic 2]

1. Para el siguiente grafo sigue paso a paso el algoritmo de Kruskal.

[pic 3]

(4.00 Puntos) Coloca cada paso del algoritmo:

[pic 4] Selecciono valor 2, y evito ciclos.[pic 5][pic 6][pic 7][pic 8][pic 9][pic 10][pic 11][pic 12]

[pic 13] Selecciono valor 3, y evito ciclos.[pic 14][pic 15][pic 16][pic 17][pic 18][pic 19][pic 20][pic 21][pic 22][pic 23]

[pic 24] Selecciono valor 4, y compruebo que no existen bucles.[pic 25][pic 26][pic 27][pic 28][pic 29][pic 30][pic 31][pic 32][pic 33][pic 34][pic 35]

(1.00 Puntos) ¿Cuál es el costo asociado de tu árbol de expansión mínima resul- tante?

. . . . . .4+2+3+2+3=14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . .El costo de expansión mínimo es de 14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1. (5.00 Puntos) Diseña un algoritmo para identificar al intruso en una reunión de exa- lumnos de una cierta promoción de un colegio. En un grupo de N personas, solo una persona es intrusa, es decir desconocida por todos.  Tal persona puede estar presente en la fiesta, en caso afirmativo, nadie la conoce. Solo podemos hacer preguntas como “¿A conoce a B? “. Encuentra al intruso en el número mínimo de preguntas, en un tiempo lineal. ¿Cuál es tu algoritmo?

[pic 36][pic 37]

1. (5.00 Puntos)  N piratas han robado un cofre de tesoros.  El cofre de tesoros contiene algo de botín. Los precios individuales de cada botín serán dados en un array de enteros llamado BOTIN. Existe al menos N piratas, pero menos de 2N objetos en el cofre.

Los piratas quieren dividir el botín siguiendo las siguientes reglas:

• Cada pirata debe recibir al menos un objeto.
• Cada pirata debe recibir dos objetos como máximo.
• Cada pirata debe obtener objetos con el mismo precio en total.

Retornar posible si los piratas podrán dividir el botín de acuerdo a las reglas anterior- mente mencionadas, o imposible si ellos no lo podrán lograr. ¿Cuál es tu algoritmo?

Como entrada recibirán la cantidad de piratas N y la lista de botín a repartir. INPUT N [a, b, c]

Ejemplos:

• Caso 0:

1 {47}

Retorna posible

Sólo un pirata puede obtener un único botín

• Caso 1:

3 {10, 8, 10, 1, 1}

Retorna imposible

No se puede dividir el botín de acuerdo a las reglas. Se podría repartir el botín si uno recibiera 3 objetos: {8,1,1}, pero va en contra de las reglas.

• Caso 2:

3 {3, 9, 10, 7, 1}

Retorna posible

Un pirata recibe {3+7}, otro {9+1}, y el otro sólo {10}

• Caso 3:

6 {1,1,1,2,1,1,1,1,1,1,1}

Retorna posible

Un pirata recibe sólo {2} y los otros {1+1}

• Caso 4:

2 {40, 1, 42}

Retorna .Imposible..

Completar este último caso con el resultado de su algoritmo

[pic 38][pic 39]

1. (1.00 Puntos) Muestre la estructura de datos final de conjuntos disjuntos (union-find) después de ejecutar todas las operaciones a continuación.[pic 40]

1. f o r        i  = 1  to  10
2. MakeSet ( i )
3. Union ( 1 , 3 )

1. Union ( 1 ,   7 )
2. Union ( 5 ,   7 )
3. Union ( 2 ,   8 )

7        Union ( 2 , 10 )

1. Union ( 6 ,   8 )
2. Union ( 4 ,   6 )
3. Union ( 1 , 9 )
4. Find Set ( 2 )
5. Find Set ( 10 )[pic 41]

[pic 42]

FindSet(2) = 2

FindSet(10) = 2

1. Miscelánios:

1. (0.25 Puntos) Del análisis amortizado podemos decir:

Analiza problemas de inserción de pila y contadores binarios, para demos- trar que Fibonacci heap es erróneo.[pic 43]

Promedia el tiempo requerido para realizar una secuencia de operaciones sobre alguna estructura de datos.[pic 44]

...