Trimestre 2009 Otoño
Entrega: 19 de octubre
2009 en clase.
[5 puntos] Demuestre por inducción que 1 + 3 + 5 + ... +
(2n-1) = n2 para toda n >= 1.
[5 puntos] Demuestre por inducción que 3n <
n! para
toda n >= 7.
[10 puntos] Demuestre que el siguiente algoritmo para calcular yz
es correcto:
x := 1
mientras z > 0 haz
si z es
impar entonces x := xy
z := z/2 (parte entera)
y := y2
regresa x
[5 puntos] Suponga que en el algoritmo anterior z tiene n bits.
Calcule el
número máximo M(n) de multiplicaciones que realiza el
algoritmo. Observe que hay un máximo de dos multiplicaciones en
el cuerpo del ciclo.
[15 puntos] Para cada una de las siguientes parejas de funciones
decida si f(n) es O(g(n)) o no. Diga qué es lo correcto y
demuéstrelo: