a) 1 und 4

b) 1 und 2

c) 2 und 4

d) 1 und 3

e) 2 und 3

f) 1 und 3

g) 2 und 3

h) 3 und 4

a) Bucket 1: 27 - 75 Bucket 3: 44 - 4 - 0 Bucket 5: 13 - 65 - 33 Bucket 7: 46 - 26

b) Es werden nur die ungeraden Buckets befüllt, da 2 und 8 nicht teilerfremd sind.

c) Bucket 0: 12 S Bucket 1: 33 D Bucket 2: 66 S Bucket 3: 28 P Bucket 4: 14 D Bucket 5: 6 S Bucket 6: 18 D Bucket 7: 5 D Bucket 8: 15 P Bucket 9: 9 D

a)

void radixSort (LinkedList<Integer> list) {
	LinkedList<Integer>[] bs = new LinkedList[];
	for (int i = 0; i < bs.length; i++) {
		bs[i] = new LinkedList();
	}
	for (int i = 0; i < 10; i++) {
		for (Integer x: list) {
			int b = (x/Math.pow(10,i)) % 10;
			bs[b].addLast(x);
		}
		list.clear();
		for (int i = 0; i < bs.length; i++) {
			list.addAll(bs[i]);
			bs[i].clear();
		}
	}
}

b)

...
int b = ((x/Math.pow(10,i)) % 10) + 9;
...

a)

long countNaive(int n) {
	if (n == 0 || n == 1) {
		return 1;
	}
	int sum = 0;
	for (int i = 0; i < n; i++){
		sum = sum + countNaive(i) * countNaive(n-1-i);
	}
	return sum;
}
 
long countDP (int n) {
	long[] mem = new long[];
	mem[0] = 1;
	mem[1] = 1;
	return countDPH(mem, n);
}
 
private long countDPH (long[] mem, int n) {
	if (mem[n] != 0) {
		return mem[n];
	} else {
		int sum = 0;
		for (int i = 0; i < n; i++){
			sum = sum + countDPH(i) * countDPH(n-1-i);
		}
		mem[n] = sum;
		return sum;
	}
}
 
long countIter (int n) {
	...
	for (int k = 2; k < n+1; k++){
		for (int i = 0; i < n; i++){
			mem[k] = mem[k] + mem[i] * mem[n-1-i];
		}
	}
	...
}

a) Ergebnis: A 14, E 18, H4 6, H7 3, M 2, W 0

b) siehe Tafeluebungsfolien

c) M - H7, M - W, M - H4, A - E, A - H4 oder A - W

d) nein: bei 4 Knoten ungerader Grad nein: nicht mal ein Eulerweg

class MaxFlowMinCut {
    void erreichbareVerteiler(Verteiler v, List<Verteiler> ev){
        if(!ev.contains(v)){
            ev.add(v);
            for(Rohr r : v.rohre){
                this.erreichbareVerteiler(r.a, ev);
                this.erreichbareVerteiler(r.e, ev);
            }
        }
    } 
 
    double schnittDurchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite){
        double sum = 0;
        for(Verteiler v : quelleSeite){
            for(Rohr r : v.rohre){
                if(senkeSeite.contains(r.a) || senkeSeite.contains(r.e)){
                    sum += r.df;                    
                }
            }
        }
        return sum;
    } 
 
 
    double durchfluss(List<Verteiler> quelleSeite, List<Verteiler> senkeSeite, Verteiler senke){
	Verteiler[] ssa = senkeSeite.toArray(new Verteiler[senkeSeite.size()]);
	double df = schnittDurchfluss(quelleSeite, senkeSeite);
	for(Verteiler v : ssa){
		if(!v.equals(senke)){
			quelleSeite.add(v);
			senkeSeite.remove(v);
			df = Math.min(df, durchfluss(quelleSeite, senkeSeite));
			senkeSeite.add(v);
			quelleSeite.remove(v);
		}
	}
	return df;		
     }
 
}