===== Forendiskussionen =====

  * [[https://fsi.cs.fau.de/forum/thread/13555-Altklausur-SS15-2-Loesungsvorschlag-Baeume]] Aufgabe 2
  * [[https://fsi.cs.fau.de/forum/thread/13531-Altklausur-SS15-5-DAG]] Aufgabe 5 - **eingefügt!**
  * [[https://fsi.cs.fau.de/forum/thread/13536-Vorschlag-fuer-Aufgabe-6-Dynamische-Programmierun]] Aufgabe 6 **eingefügt!**
  * [[https://fsi.cs.fau.de/forum/thread/13535-Vorschlag-fuer-Altklausur-SS-15-Aufgabe-7-Sorti]] Aufgabe 7 **eingefügt!**

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

==== Aufgabe 1 - Wissensfragen (16) ====
  * a) 1 und 4
  * b) 1 und 2
  * c) 4 *Edit*(und 2) vgl. Vl 14 S. 85 *Edit*
  * Erneuter Edit von jemand anderem: 4 ist nicht richtig, der Laufzeitaufwand bei Prim ist O(n*log n + e). O(n + m) = O(max(n, m)), n*log(n) ist hier max, darum stimmt O(n*log(n)). Ausserdem ist 3 sehr wohl richtig: Das steht exakt so in der Vorlesung, Kruskal hat O(e*log e).

  * d) 1 und 4 (zu 2: Interfaces weder implementieren noch erben von Object => siehe JLS: http://docs.oracle.com/javase/specs/jls/se7/html/jls-9.html#jls-9.2)
  * e) 3 und 4
  * f) 1
  * g) 2 und 3
  * h) 1 und 4
==== Aufgabe 2 - Bäume (9) ====

[[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html | Tool]]
==== Aufgabe 3 - Graphen (18) ====
a) Endergebnis: 0,2,4,7,6,7 ---> Falsch: Von A nach F kommt man mit Pfad A->B->C->F mit Kosten 5, 7 kann also nicht stimmen. Lösung ist: 0,2,4,7,6,5)

b) A->B->C->F->E->D, Distanz 7.

c)

  * B, A
  * A, D
  * E, D
  * E, F
  * F, C

Alternativ:

  * B, C
  * F, C
  * E, F
  * E, D
  * D, A

d)

  * Stark zusammenhängend: keine
  * Schwach zusammenhängend: 1, 6
  * Zusammenhängend: 3
  * Nicht zusammenhängend: 2, 4, 5

==== Aufgabe 4 - Rekursion (11) ====

Live auf ideone.com mit AuD-Beispiel: http://ideone.com/jr02d3

<code java>static <T> List<List<T>> helfer(T[] s, int idx) {
	// Rückgabe pms ist Potenzmenge von s ab index idx
	List<List<T>> pms = new ArrayList<List<T>>();
	if (idx >= s.length) {
		// Basisfall
		pms.add(new ArrayList<T>());
	} else {
		// aktuelles Kopfelement bestimmen
		T kopf = s[idx];
		
		// Potenzmenge der Restliste bestimmen
		List<List<T>> potRest = helfer(s, idx + 1);
		
		// Ergebnisse zusammenführen
		for (List<T> ohneKopf : potRest) {
			List<T> mitKopf = new ArrayList<>(ohneKopf); // *nocH* ohne Kopf
			mitKopf.add(kopf);
			
			pms.add(ohneKopf);
			pms.add(mitKopf);
		}
	}
	return pms;
}</code>
==== Aufgabe 5 - Gerichtete azyklische Graphen (15) ====
<code java>boolean eval(HashSet<String> tv) {
    if (this == BDD.TRUE) return true;
    if (this == BDD.FALSE) return false;
    return tv.contains(v) ? trueC.eval(tv) : falseC.eval(tv);
}

boolean isDAG(HashSet<BDD> p) {
    if (p.contains(this)) return false;
    p.add(this);
    if (trueC != null && !trueC.isDAG(p)) {
      return false;
    }
    if (falseC != null && !falseC.isDAG(p)) {
      return false;
    }
    p.remove(this);
    return true;
}</code>
==== Aufgabe 6 - Dynamische Programmierung (17) ==== 
a) Verschachtelte Rekursion

b, c)
<code java>
class DynProg {

	private int[] dp;
	
	public DynProg(int max) {
		dp = new int[max];
	}

	int fDP(int n) { // Dynamische Programmierung
		int fn = 1; // Basisfall n < 3 trivial
		
		// fn schon einmal berechnet?
		if (n <= dp.length && dp[n-1] != 0) {
			fn = dp[n-1];
		} else if (n >= 3) { // fn muss noch berechnet werden
			if (n <= dp.length) {
				fn = fDP(n - 2*fDP(n - fDP(n-1))) + 1;
				dp[n-1] = fn;
			} else {
				fn = f(n);
			}
		}
		return fn;
	}
}
</code>

d)

Hier sind viele Varianten denkbar.
<code java>
public static int fIter(int n) { // Iterativ
	int k = 1; // Zähler
	int fk = 1;
	
	int z = 2;
	for (; k<=n; k++) {
		if (z == 0) {
			fk++;
			z = 2 * fk - 1;
		}
		else {
			z--;
		}
	}
	
	return fk;
}
</code>
==== Aufgabe 7 - Sortieren (16) ====
Mit System.out.println() Aufrufen zum Testen:
<code java>
public class MergeSortUsing4Lists {
     public static void mergeSortExtern(LinkedList<Integer> b) {
         assert b != null;
         assert b.size() > 0;

         LinkedList<Integer> b0 = new LinkedList<>();
         LinkedList<Integer> b1 = new LinkedList<>(b.subList(0, b.size() / 2));
         LinkedList<Integer> b2 = new LinkedList<>(b.subList(b.size() / 2, b.size()));
         LinkedList<Integer> b3 = new LinkedList<>();

         merge(1, b0, b1, b2, b3);

         b.clear();
         b.addAll(b0);
         b.addAll(b1);
     }

     public static void merge(int len, LinkedList<Integer> b0, LinkedList<Integer> b1, LinkedList<Integer> b2,
             LinkedList<Integer> b3) {
         LinkedList<Integer> target = b0; // alternating between b0 and b3

         do {
             System.out.println();
             System.out.println(b0);
             System.out.println(b1);
             System.out.println(b2);
             System.out.println(b3);
             System.out.println();
             int z1 = 0, z2 = 0; // counter for the already stored integers from
                                 // b1/b2 up to len

             // if possible, store integers from b1 AND b2
             while (!b1.isEmpty() && !b2.isEmpty() && z1 < len && z2 < len) {
                 // Wegen <= ist es stabil
                 if (b1.getFirst() <= b2.getFirst()) {
                     target.addLast(b1.removeFirst());
                     z1++;
                 } else {
                     target.add(b2.removeFirst());
                     z2++;
                 }
             }

             // if there are still integers from b1
             while (!b1.isEmpty() && z1 < len) {
                 target.addLast(b1.removeFirst());
                 z1++;
             }

             // if there are still integers from b2

             while (!b2.isEmpty() && z2 < len) {
                 target.addLast(b2.removeFirst());
                 z2++;
             }

             target = target == b0 ? b3 : b0;

         } while (!b1.isEmpty() || !b2.isEmpty());
         // b3 is not empty => recursion call!

         if (!b3.isEmpty()) {
             merge(2 * len, b1, b0, b3, b2);
         } else {
             System.out.println();
             System.out.println(b0);
             System.out.println(b1);
             System.out.println(b2);
             System.out.println(b3);
             System.out.println();
         }
     }

     public static void main(String[] args) {
         LinkedList<Integer> a_empty = new LinkedList<Integer>();
    	 mergeSortExtern(a_empty);

         LinkedList<Integer> a = new LinkedList<Integer>(
                 Arrays.asList(10, 2, 1, 7, 6, 9, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));

         mergeSortExtern(a);

         // odd number of elements (added number 19)
         LinkedList<Integer> a_odd = new LinkedList<Integer>(
                 Arrays.asList(10, 2, 1, 7, 6, 9, 19, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));

         mergeSortExtern(a_odd);
     }
 }</code>
==== Aufgabe 8 - Backtracking (18) ====
<code java>
LinkedList<int[]> helfer(int mL, int kL, int b, int mR, int kR) {
	LinkedList<int[]> erg = new LinkedList<>();
	if(mL < 0 || kL < 0 || mR < 0 || kR < 0) {
		// Abbruch wegen negativer Personenzahl
		return null;
	} else if(mem[mL][kL][b][mR][kR]) {
		// Abbruch weil Zustand schon besucht
		return null;
	} else if((mL > 0 && mL < kL) || (mR > 0 && mR < kR)) {
		// Abbruch zu viele Kannibalen an einem der Ufer
		return null;
	} else if(mL == 0 && kL == 0 && b == 1) {
		// Zielzustand erreicht
		erg.add(new int[] { mL, kL, b, mR, kR });
		return erg;
	} else {
		// zulaessiger Zwischenzustand
		erg.add(new int[] { mL, kL, b, mR, kR });

		for(int[] fahrt : denkbar[b]) {
			// probiere jede denkbare fahrt, die am Ufer b beginnt
			mem[mL][kL][b][mR][kR] = true;
			LinkedList<int[]> list = helfer(mL - fahrt[0], kL - fahrt[1], (b + 1) % 2, mR + fahrt[0], kR + fahrt[1]);
			if(list != null) {
				erg.addAll(list);
				return erg;
			}
			mem[mL][kL][b][mR][kR] = false;
		}
	}
	return null;
}
</code>