Algoritmer och Datastrukturer
Frslag till lsning fr ngra vningar i kurslitteraturen.
7.5, 7.19, 7.25, 8.1, 8.4, 8.5, 8.6 och 8.14(finns inte i den nya boken)
1. (7.5 from the course book) We use the program
public static long gcd(long a, long b){
if(b==0)
return a;
else
return gcd(b,a%b);
}
then the computation of gcd(1995,1492) goes as follows: the value returned is gcd(1492,503). This value is computed as follows: the value returned is gcd(503,486). We continue by using --> to indicate the values returned:
gcd(503,486) --> gcd(486,17) --> gcd(17,10)--> gcd(10,7) --> gcd(7,3) --> gcd(3,1)--> gcd(1,0) --> 1
2. (7.19) In the following program to count the number of ones in the binary representation of a number we use the definition of being even: that the reminder of the division by two is 0!
public static int ones(int n){
if(n==0)
return 0;
else if(n%2==0)// n is even
return ones(n/2);
else // n is odd
return 1+ones(n/2);
}
3. (7.25)
public static void permute(String a){
// because we need to change position among characters in the
// string, it is easier to work with the array of characters.
// because the recursion will be done by choosing what character
// to exchange with all others, the second argument indicates that we
// start with the first character.
permute(a.toCharArray(),0);
}
private static void permute(char[] a, int low){
if(low == a.length-1) // the character we have to exchange
// with all following ones is the last one,
// we are done. print this permutation!
System.out.println(a);
else{ // exchange the character at position low with every
// character that follows, and for this change consider all
// permutations upwards:
for(int i = low; i < a.length; i++){
swap(a,low,i);
permute(a,low+1);
swap(a,i,low);
}
}
}
private static void swap(char [] a, int p, int q){
char tmp = a[p];
a[p] = a[q];
a[q] = tmp;
}
4. (8.1)
1. insertion sort:(see code in the course book) We only show the changes in the array!!
8 1 4 1 5 9 2 6 5
8 8 4 1 5 9 2 6 5
1 8 4 1 5 9 2 6 5
1 8 8 1 5 9 2 6 5
1 4 8 1 5 9 2 6 5
1 4 8 8 5 9 2 6 5
1 4 4 8 5 9 2 6 5
1 1 4 8 5 9 2 6 5
1 1 4 8 8 9 2 6 5
1 1 4 5 8 9 2 6 5
1 1 4 5 8 9 9 6 5
1 1 4 5 8 8 9 6 5
1 1 4 5 5 8 9 6 5
1 1 4 4 5 8 9 6 5
1 1 2 4 5 8 9 6 5
1 1 2 4 5 8 9 9 5
1 1 2 4 5 8 8 9 5
1 1 2 4 5 6 8 9 5
1 1 2 4 5 6 8 9 9
1 1 2 4 5 6 8 8 9
1 1 2 4 5 6 6 8 9
1 1 2 4 5 5 6 8 9
2. quicksort with no cutoff and choosing the pivot as the middle element (before starting partition we send the pivot to the last place, instead, median of three can send it to the last but one place!) I underline the pivot. I show the fragment inspected by the recursive calls
8 1 4 1 5 9 2 6 5
^
8 1 4 1 5 9 2 6 5 (five and five have changed place!)
^
2 1 4 1 5 9 8 6 5
^
2 1 4 1 5 9 8 6 5 (five and five have changed place!)
2 1 4 1
^
2 1 4 1 (one and one have changed place!)
^
1 2 4 1
^
1 1 4 2
1 this is sorted (base case of the recursion!)
1 is left in its place!
4 2
^
2 4
^
2 4 four changes place with four!
sort the empty array before 2
2 is left in its place!
4 is already sorted!
5 is left in its place!
now this half is ready, the second half is sorted in the same way as the first half!
5. (8.4)
1. Insertion sort runs in linear time when the keys are all alike. If N is the size of the array, there are N iterations and what is done in each iteration is constant time because the inner for loop is never entered (it is allways executed zero times)!
2. Quick sort runs in O(N log N) with all keys alike if the partition algorithm stops at elements that are equal to the pivot (as in the code presented in the book). Partition continues to be linear, many elements change place, but it stops in the middle of the array, making the 2 recursive calls in fragments that are half the size.
6. (8.5)
1. Insertion sort runs in linear time when the keys are sorted. If N is the size of the array, there are N iterations and what is done in each iteration is constant time because the inner for loop is never entered (it is allways executed zero times)!
2. Quick sort runs in O(N log N) with sorted keys. The partition algorithm will stop at the middle of the array.
7. (8.6)
1. Insertion sort runs in cuadratic time when the keys are sorted in reverse order. If N is the size of the array, there are N iterations and what is done in each iteration is O(N) because the inner for loop allways run down to 0, when it comes to the last element, N iterations! and what is done in this inner loop is constant time.
2. Quick sort runs in O(N log N) with keys sorted in reversed order. The partition algorithm will stop at the middle of the array.
8. (8.19)
1. A quadratic solution to the question whether there are 2 elements in an array summing up to k (possibly one element considered twice!)
public static boolean badSum2k(int[]a, int k){
int n = a.length;
for(int i = 0;i < n; i++)
for(int j = i;j < n; j++)
if(a[i]+a[j]==k)
return true;
return false;
}
2. An O(N log N) solution to the same problem, based in that we can sort in O(N log N) nad search in O(log N) in a sorted array!
public static boolean sum2k(int[]a, int k){
int n = a.length;
Arrays.sort(a); // this is quicksort!!
for(int i = 0;i < n; i++){
int j = Arrays.binarySearch(a,k-a[i]);
if(j>0)
return true;
}
return false;
}