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) {
        //prepare sufficient buckets bs with empty lists:
	LinkedList<Integer>[] bs = new LinkedList[10];
	for (int i = 0; i < bs.length; i++) {
		bs[i] = new LinkedList<>();
	}
        //for each segment of the Integer radix...
	for (int i = 0; i < 10; i++) {
                //...distribute values into buckets:
		for (Integer x: list) {
			int b = (int) (x/Math.pow(10,i)) % 10;
			bs[b].addLast(x);
		}
                //...recollect values from buckets:
		list.clear();
		for (int j = 0; j < bs.length; j++) {
			list.addAll(bs[j]);
			bs[j].clear();
		}
	}
}

b)

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

oder einfacher:

...
bs[b + 9].addLast(x);

a)

long countNaive(int n) {
	if (n == 0 || n == 1) {
		return 1;
	}
	long sum = 0; 
	for (int i = 0; i < n; i++) {
		sum += countNaive(i) * countNaive(n-1-i);
	}
	return sum;
}

b)

long countDP (int n) {
	long[] mem = new long[n + 1];
	mem[0] = 1;
        mem[1] = 1;
 
	return countDPH(mem, n);
}
 
private long countDPH (long[] mem, int n) {
        // Lookup
	if (mem[n] != 0) {
		return mem[n];
	} else {
		long sum = 0;
		for (int i = 0; i < n; i++) {
			sum += countDPH(mem, i) * countDPH(mem, n-1-i);
		}
                // Memoization
		mem[n] = sum;
		return sum;
	}
}

oder schöner:

private long countDPH (long[] mem, int n) {
	// Lookup
        if (mem[n] != 0) {
		return mem[n];
	}
	for (int i = 0; i < n; i++) {
            // Berechnung + Memoization
            mem[n] += countDPH(mem, i) * countDPH(mem, n-1-i);
	}
	return mem[n];
}

c)

long countIter (int n) {
	...
	for (int k = 2; k < n+1; k++) { // for-Schleife fuer bottom-up
		for (int i = 0; i < k; i++) {
			mem[k] = mem[k] + mem[i] * mem[k-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)){  // v.equals ist gleich zu == (Weil es von Object erbt, aber .equals nicht überschreibt)
			// Hier kann man noch checken, ob zu v auch eine Kante aus quelleSeite existiert, aber nicht notwendig, da der Cut nur länger weden würde -> nur geringere Laufzeit
			quelleSeite.add(v);
			senkeSeite.remove(v);
			df = Math.min(df, durchfluss(quelleSeite, senkeSeite, senke));
                        //"Backtracking"
			senkeSeite.add(v);
			quelleSeite.remove(v);
		}
	}
	return df;		
     }
 
}