===== Forendiskussionen =====

===== Lösungsversuch =====

==== Aufgabe 1 Wissensfragen ====
** 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

==== Aufgabe 2 Streupeicherung ====
** 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

==== Aufgabe 3 RadixSort ====
** a) **
<code java>
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();
		}
	}
}
</code>
** b) **
<code java>
...
int b = ((int) (x/Math.pow(10,i)) % 10) + 9;
...
</code>

oder einfacher:
<code java>
...
bs[b + 9].addLast(x);
</code>
==== Aufgabe 4 Dynamische Programmierung ====
**a)**
<code java>
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;
}
</code>

**b)**

<code=java>
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;
	}
}
</code>

oder schöner:

<code java>
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];
}
</code>

**c)**

<code=java>
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];
		}
	}
	...
}
</code>


==== Aufgabe 5 Graphen ====
** 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

==== Aufgabe 6 Rekursion ====
<code java>
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;		
     }
     
}
</code>