Solución examen final   :    Guillermo Escobar P   cod    256243

1)

 An array  A[1_n]  contains all of the integers from 0 to n except one. It would be easy to determine the missing integer in ntime by using an auxiliary array B[0…n ]  to record which numbers appear in A. In this problem, however, we cannot access an entire integer in A with a single operation. The elements in A are represented in binary , and the only operation we can use to access them is the "fetch the jth bit of A[i]," which takes constant time. Show that if we use only this operation, we can still determine the missing integer in O(n) time. (Hint: bucket sort binary). 

Solución :

Tomamos el bit de menos  significancia  de los n bits dados  de derecha a izquierda.  Entonces se forman dos grupos de elementos uno que tiene el bit  con 0   y  el otro el que tiene  bit en  1 .  Dado que hace falta un elemento, uno de los grupos de bits es  mayor que el otro.  Tomamos  el grupo de bits mas pequeño ,  éste arreglo queda  con  n/2 comparado con el arreglo  original.

Ahora volvemos a realizar el mismo procedimiento a este arreglo pero tomando el sugundo de menos significncia . Asi quedan nuevamente dos grupos los de bit en 0  y los de bit en 1 en.   Tomamos  el grupo de bits mas pequeño ,  éste arreglo queda  con  n/4 comparado con el arreglo  original.

Si continuamos aplicando el procedimiento al arreglo que queda  llegaremos al bit perdido.
Entonces  se tiene un tiempo de ejecución de 

T(n)= n + n/2 + n/4  + ... + 1     =2n=O(n).

2)
 Draw the recursion tree for the Merge-Sort  on an array of 16 elements. Explain why memorization is ineffective in speeding up a good divide-and conquer algorithm such as Merge-Sort.

Solucion ;

Aqui no es necesario utilizar la memorizacion , dado que el sort de merge no tiene subproblemas traslapados.  La memorizacion no ayudaria porque un subproblema es totalmente distinto de otro.

3).
 Professor Midas drives an automobile from Newark to Reno along Interstate 80. His car’s gas tank, when full, holds enough gas to travel n miles, and his map gives the distances between gas stations on his route. The professor wishes to make as few gas stops as possible along the way. Give an efficient method by which Professor Midas can determine at which gas stations he should stop, and prove that your strategy yields an optimal solution.

Supondremos que existen G gasolineras en la ruta que sigue el profesor entre
Newark y Reno, incluyendo una en la ciudad destino, y que están numeradas del 0 (gasolinera en Newark) a G–1 (la situada en Reno).
Supondremos además que disponemos de un vector con la información que
tiene el profesor sobre las distancias entre ellas:
 DISTANCIA = Arreglo [1..G-1]
de forma que el i-ésimo elemento del vector indica los kilómetros que hay entre las gasolineras i–1 e i. Para que el problema tenga solución hemos de suponer que ningún valor de ese vector es mayor que el número n de kilómetros que el profesor puede recorrer sin recargar.
Ell algoritmo voraz pedido va a consistir en intentar recorrer el mayor número posible de kilómetros sin recargar, esto es, tratar de ir desde cada gasolinera en donde se pare a recargar a la más lejana posible, así hasta llegar al  destino.
Para demostrar la validez de este algoritmo voraz, sean x1,x2,...,xs las gasolineras en donde este algoritmo decide que hay que parar a recargar, y sea y1,y2,...,yt otro posible conjunto solución de gasolineras. Llamaremos X a un automóvil que sigue la primera solución, e Y a un automóvil que se guía por la segunda. Sea N el número  total de kilómetros a recorrer (distancia entre las dos ciudades), y sea D[i] la distancia recorrida por el profesor Midas hasta la i-ésima gasolinera (1 ≤i ≤G–1). Es decir, 

Lo que tenemos que demostrar es que s ≤t, puesto que lo que queríamos
minimizar era el número de paradas a realizar. Para probarlo, basta con demostrar
que xk ≥yk para todo k.

En primer lugar, como ambas descomposiciones son distintas, sea k el primer
índice tal que xk ≠yk. Podemos suponer que k = 1, puesto
que hasta xk–1 los viajes son iguales, y en la gasolinera xk–1 ambos vehículos
llenan su tanque completamente.

Si x1 ≠y1 entonces x1 > y1, pues x1 era la gasolinera más alejada a donde podía viajar el vehiculo sin recargar.  Además, también se tiene que x2 ≥y2, pues x2 era la gasolinera más alejada a donde podía viajar desde x1 el vehiculo sin recargar.
 Para probar este hecho, supongamos por reducción al absurdo que y2 fuera estrictamente mayor que x2.
Pero si Y consigue ir desde y1 a y2 es que hay menos de n kilómetros entre ellas, es  decir, D[y2] – D[y1] < n.
Por tanto desde x1 también hay menos de n kilómetros hasta y2, esto es,
D[y2] – D[x1] < n
puesto que D[y1] < D[x1]. Entonces el método no hubiera escogido x2 como
siguiente gasolinera a x1 sino y2, porque el algoritmo busca siempre la gasolinera más alejada de entre las que alcanza.
Repitiendo el proceso, vamos obteniendo en cada paso que xk ≥yk para todo k,
hasta llegar a la ciudad destino, lo que demuestra la hipótesis.