===== 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
static List> helfer(T[] s, int idx) {
// Rückgabe pms ist Potenzmenge von s ab index idx
List> pms = new ArrayList>();
if (idx >= s.length) {
// Basisfall
pms.add(new ArrayList());
} else {
// aktuelles Kopfelement bestimmen
T kopf = s[idx];
// Potenzmenge der Restliste bestimmen
List> potRest = helfer(s, idx + 1);
// Ergebnisse zusammenführen
for (List ohneKopf : potRest) {
List mitKopf = new ArrayList<>(ohneKopf); // *nocH* ohne Kopf
mitKopf.add(kopf);
pms.add(ohneKopf);
pms.add(mitKopf);
}
}
return pms;
}
==== Aufgabe 5 - Gerichtete azyklische Graphen (15) ====
boolean eval(HashSet 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 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;
}
==== Aufgabe 6 - Dynamische Programmierung (17) ====
a) Verschachtelte Rekursion
b, c)
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;
}
}
d)
Hier sind viele Varianten denkbar.
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;
}
==== Aufgabe 7 - Sortieren (16) ====
Mit System.out.println() Aufrufen zum Testen:
public class MergeSortUsing4Lists {
public static void mergeSortExtern(LinkedList b) {
assert b != null;
assert b.size() > 0;
LinkedList b0 = new LinkedList<>();
LinkedList b1 = new LinkedList<>(b.subList(0, b.size() / 2));
LinkedList b2 = new LinkedList<>(b.subList(b.size() / 2, b.size()));
LinkedList b3 = new LinkedList<>();
merge(1, b0, b1, b2, b3);
b.clear();
b.addAll(b0);
b.addAll(b1);
}
public static void merge(int len, LinkedList b0, LinkedList b1, LinkedList b2,
LinkedList b3) {
LinkedList 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 a_empty = new LinkedList();
mergeSortExtern(a_empty);
LinkedList a = new LinkedList(
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 a_odd = new LinkedList(
Arrays.asList(10, 2, 1, 7, 6, 9, 19, 13, 6, 3, 5, 8, 4, 11, 2, 6, 42));
mergeSortExtern(a_odd);
}
}
==== Aufgabe 8 - Backtracking (18) ====
LinkedList helfer(int mL, int kL, int b, int mR, int kR) {
LinkedList 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 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;
}