Introduction to algorithms 3rd. edition
THOMAS H. CORMEN
CHARLES E. LEISERSON
RONALD L. RIVEST
CLIFFORD STEIN
Ejercicios
1.1-1 Organizar un padrón electoral; diseñar la carcasa de un coche.
1.1-2 Gastar los mínimos recursos (papel, nafta, horas de cierta maquinaria).
1.1-3 Lista doblemente enlazada: fortaleza: fácil inserción/borrado en cualquier lado. Debilidad: para llegar a un elemento se requiere acceder a todos los anteriores.
1.1-4 Que uno tiene que volver al punto de partida y el otro no. Que en uno los caminos son en cualquier sentido y en el otro hay que elegir un camino según el sentido.
1.1-5 Marcar un número de teléfono: sólo se admite el número exacto. Calcular las cantidades de comida de una dieta: se puede aproximar. Realizar una comida con una receta: las cantidades de cada ingrediente no tienen que ser exacta, los minutos de cocción, batido, etc. también se pueden aproximar.
1.2-1 Un programa de dibujo de gráficos / de manejo de un plotter: calcular los puntos de una curva, una calculadora de bolsillo: entre otras cosas tiene que interpretar las fórmulas y realizar las operaciones; programa de manejo de un lavarropas: el usuario pone el programa que quiere (una secuencia de etapas) y el lavarropas las ejecuta.
1.2-2
8 n^2 < 64 n lg n
n < 8 lg n
n <~ 40 (valor entero de lg n más cercano: 5 <=> n = 32)
1.2-3
100 n^2 < 2^n
lg (100 n^2) < lg 2^n
lg 100 + 2 lg n < n
lg 100 < n - 2 lg n
7 <~ n - 2 lg n
16 <~ n
Problemas
f(n) = [microseconds]
1 s = 1.000.000
µs
1 m = 1.000.000 * 60
µs
|
1 second
|
1 minute
|
1 hour
|
1 day
|
1 month
|
1 year
|
1 century
|
lg n
|
2^1.000.000
|
2^1.000.000*60
|
2^1.000.000*3.600
|
2^1.000.000*3.600*24
|
2^1.000.000*3.600*24*30
|
2^1.000.000*3.600*24*365
|
2^1.000.000*3.600*24*36.500
|
\/¯n
|
1.000.000^2
|
|
|
|
|
|
|
n
|
1.000.000
|
|
|
|
|
|
|
n lg n
|
~ 2^16
|
|
|
|
|
|
|
n^2
|
1.000
|
|
|
|
|
|
|
n^3
|
100
|
|
|
|
|
|
|
2^n
|
~ 20
|
|
|
|
|
|
|
n!
|
~ 10
|
|
|
|
|
|
~ 17
|
1 second:
n lg n < 1.000.000
n lg n <~ 2^20 = 2^16 . 2^4 /// 16+4=20 y lg 2^16=2^4
n <~ 2^16
n! < 1.000.000
n <~ 10
1 century:
n! < 1.000.000*3.600*24*36.500
n <~ 17
| 1000000*3600*24*36500= |
3.1536E+15 |
| 3153600000000000/2= |
1.5768E+15 |
| 1576800000000000/3= |
5.256E+14 |
| 525600000000000/4= |
1.314E+14 |
| 131400000000000/5= |
2.628E+13 |
| 26280000000000/6= |
4.38E+12 |
| 4380000000000/7= |
6.2571E+11 |
| 625714285714.286/8= |
7.8214E+10 |
| 78214285714.2857/9= |
8690476190 |
| 8690476190.47619/10= |
869047619 |
| 869047619.047619/11= |
79004329 |
| 79004329.004329/12= |
6583694.08 |
| 6583694.08369408/13= |
506438.006 |
| 506438.006438007/14= |
36174.1433 |
| 36174.1433170005/15= |
2411.60955 |
| 2411.6095544667/16= |
150.725597 |
| 150.725597154169/17= |
8.8662116 |
| 8.86621159730404/18= |
0.49256731 |
Siguiente: página 22 (43/1313), Exercises
2.1-1
Using Figure 2.2 as a model, illustrate the operation of I NSERTION-SORT on the array A D h31;41;59;26;41;58i.
2.1-2 Rewrite the INSERTION-SORT procedure to sort into nonincreasing instead of non-decreasing order.
INSERTION-SORT .A/
1 for j = 2 to A.length
2 key = A[j]
3 // Insert j into the sorted sequence A[1..j-1].
4 i = j - 1
5 while i > 0 and A[i] < key
6 A[i - 1] = A[i]
7 i = i - 1
8 A[i + 1] = key
2.1-3
Consider the searching problem:
Input: A sequence of n numbers A = (a 1 ;a 2 ;...;a n ) and a value v.
Output: An index i such that v = A[i] or the special value NIL if v does not appear in A.
Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.
i = A.length
while i >= 0 and A[i]<>v
i = i-1
Loop invariant: At the start of each iteration none of the elements at the right hand side are the searched one. And the searched element is either the one at the current iteration or any of the others at the left hand side, if it exists.
Initialization: It is true prior to the first iteration of the loop.
At the first loop, all of the array is at the left hand side. Only the current element is being looked at. The right hand side has no elements.
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
At each iteration, which goes through downwards, the elements on the right hand side are all failed to the searched condition. And the left ones aren't yet tested.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
When the loop terminates, it was either because all the array stand at the right hand side or the last one examined was the searched one. The left hand side, consists of the elements not examined, if any.
2.1-4
Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an n+1-element array C. State the problem formally and write pseudocode for adding the two integers.
The binary sum of 2 numbers is:
For all the digits:
0 if both digits and the overflow is 0
1 if one and only one of the 3 is 1
0 if 2 of them are 1, and carrying overflow=1 since that
1 if the 3 are 1, and carrying overflow=1 either
The overflow is always taken from a less-significant-ward digit (hence the least one has not overflow).
overflow='0'
for i=0 to A.length // A.length = B.length
if overflow='0'
if A[i]='0'
C[i] = B[i]
else
if B[i]='0'
C[i]='1'
else
C[i]='0'
overflow='1'
else
if A[i]='0'
if B[i]='0'
C[i]='1'
overflow='0'
else
C[i]='0'
else
C[i]=B[i]
C[i]=overflow // exit loop with i = C.length = A.length+1
2.2-1 n^3
2.2-2
// SELECTION-SORT
for i=0 to A.length-1
jMin = i
min = A[jMin]
for j = i+1 to A.length
if A[j] < min
jMin = j
min = A[jMin]
A[jMin] = A[i]
A[i] = min
Loop invariant: At the start of each outer iteration the elements at the left side are sorted.
Initialization: It is true prior to the first iteration of the loop.
At
the first loop, all of the array is at the right side. The left side is void and since it has none element it's "sorted".
Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
At
each outer iteration, the current element is exchanged with the least from the right side, taking part of the left side in the next iteration and being the least of the remainder means to be is order with the others.
Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.
When
the loop terminates, All the array is at the left side, except the last element which is the remainder and therefore is the greater of all, resulting in all the array being sorted.
// SELECTION-SORT
for i=0 to A.length-1 // c1 n
jMin = i // c2 n-1
min = A[jMin] // c3 n-1
for j = i+1 to A.length // c4 sum(i=1..n) i
if A[j] < min // c5 sum(i=1..n-1) i
jMin = j // c6 sum(i=1..n-1) ti
min = A[jMin] // c7 "
A[jMin] = A[i] // c8 n-1
A[i] = min // c9 n-1
Best case: ti=0: c1 n + (c2+c3+c8+c9)(n-1)+c4 n (n+1)/2 -1 + c5 n (n-1) /2=
= (c1+c2+c3+c8+c9) n - (c2+c3+c8+c9) + (c4 n^2 + c4 n) / 2 - 1 + (c5 n^2 -c5 n) / 2 =
= (c1+c2+c3+c8+c9) n - (c2+c3+c8+c9) + (c4+c5) n^2 / 2 + (c4 - c5) n / 2 - 1=
= (c1+c2+c3+c8+c9+c4/2-c5/2) n - (c2+c3+c8+c9) + (c4+c5) n^2 / 2 - 1= a n^2 + b n + c
Worst case ti=i: c1 n + (c2+c3+c8+c9) (n-1) + c4 n (n+1) / 2 - 1 + (c5+c6+c7) n (n-1) / 2 =
= ... = (c1+c2+c3+c8+c9+c4/2-c5/2-c6/2-c7/2) n - (c2+c3+c8+c9) + (c4+c5+c6+c7) n^2 / 2 - 1= a n^2 + b n + c
2.2-3
average case: sum(i=0..n) i / n = [n (n+1) /2 -1]/n ~ n/2
worst case: n
O() notation:
average case: O(n) (like the average running time but coefficient omitted).
worst case: O(n)
2.2-4 To first check if the input already meets the supposed output so as to avoid any processing.
2.3-1
Using Figure 2.4 as a model, illustrate the operation of merge sort on the array
A = <3;41;52;26;38;57;9;49>
2.3-2
Rewrite the M ERGE procedure so that it does not use sentinels, instead stopping
once either array L or R has had all its elements copied back to A and then copying
the remainder of the other array back into A.
MERGE (A, p, q, r)
1. n1 = q - p + 1
2. n2 = r - q
3. let L[1..n1] and R[1..n2] be new arrays
4. for i = 1 to n1
5. L[i] = A[p + i - 1]
6. for j = 1 to n2
7. R[j] = A[q + j]
8. i = 1
9. j = 1
10. k = p
11. while i<=n1 and j<=n2
12. if L[i] <= R[j]
13. A[k] = L[i]
14. i = i + 1
15. else A[k] = R[j]
16. j = j + 1
17. // end if
18. k = k+1
19. // end while
20. while i<=n1
21. A[k] = L[i]
22. i=i+1
23. k=k+1
24. //end while
25. while j<=n2
26. A[k] = R[j]
27. j=j+1
28. k=k+1
29. //end while
MERGE-SORT (A;p;r)
1. if p < r
2. q = floor((p + r)/2)
3. MERGE-SORT (A;p;q)
4. MERGE-SORT (A;q + 1;r)
2.3-3
Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence
T(n)=
{
2 if n = 2 ;
2T(n/2) + n if n = 2^k , for k > 1
is T(n)= n lgn.
2.3-4
2.3-5
2.3-5 Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against v and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is O(lg n).
BINARY-SEARCH(A, v)
p=1
q= A.length
MIENTRAS p<=q && v<> A[(p+q)/2]
SI v < A[(p+q)/2]
q= (p+q)/2-1
SI v > A[(p+q)/2]
p= (p+q)/2+1
SI p<=q
DEVOLVER (p+q)/2
SI NO
DEVOLVER NIL
BINARY-SEARCH-R(A,v,p,q)
SI p>q // c1
DEVOLVER NIL // c2
SI v= A[(p+q)/2] // c3
DEVOLVER (p+q)/2 // c4
SI v < A[truncar((p+q)/2)] // c5
DEVOLVER BINARY-SEARCH-R(A,v,p,truncar((p+q)/2)-1) // T1: T(n/2-1), excluyente con T2
SI v > A[(p+q)/2] // c6 // C=c1+c2+c3+c4+c5+c6
DEVOLVER BINARY-SEARCH-R(A,v,truncar((p+q)/2)+1,q) // T2: T(n/2-1), excluyente con T1
BINARY-SEARCH(A,v)
DEVOLVER BINARY-SEARCH-R(A,v,1,A.length)
