===== Forendiskussionen =====
  * [[https://fsi.cs.fau.de/forum/thread/14556-Klausur-WS15-Loesungsdiskusion|https://fsi.cs.fau.de/forum/thread/14556-Klausur-WS15-Loesungsdiskusion]]
  * [[https://fsi.cs.fau.de/forum/thread/14621-eine-Denkfehler-Ws2015-A4-Halde|Diskussion zur Aufgabe 4]]
===== Lösungsversuch =====

==== Aufgabe 1 Wissensfragen ====
** a) ** 1 und 3

** b) ** 2 und 3

** c) ** 2   || Ziemlich sicher, dass auch 1 richtig ist.
  * zu 1) (2. Meinung: "(stimmt hier nicht auch 1?)") => wenn man bei der linearen Suche ("< oder "=") überprüft, müsste man sicherstellen, dass die zu durchsuchende Zahlenreihe immer aufsteigend sortiert ist. Mit einer allgemeinen Methode zur linearen Suche würden die Suchen mit Sicherheit für alle anderen Fälle daneben gehen. 
  * zu 2) Lineare Suche überprüft im intervall [0:n] ob das i-te-Element == gesuchte Element ist, wenn das gesuchte Element das erste Element ist, dann ist man sofort fertig. Die binäre Suche braucht dazu mindestends noch ein schritt. 
  * zu 3) unsicher, ob das hier eine Rolle spielt ( 2.Meinung: "Denke ich nicht")
  * zu 4) scheidet aus, weil 2 richtig ist

** d) ** 3

** e) ** 1 und 4
  * Man spricht nur bei "ungerichteten" Graphen von "Grad", bei gerichteten unterscheidet man Eingangs- und Ausgangsgrad. Wenn ein Knoten ein Grad 0 hat, dann gibt es keine Kante auf ihn. Der Graph ist also bereits ab einem Knoten mit Grad 0 nicht mehr zusammenhängend. Vorausgesetzt der Graph besteht aus mehr als einem Knoten. Da nichts anderes Korrekt scheint, muss dass also so passen.
  * Ein stark zusammenhängender Graph hat zyklen, womit der Graph kein DAG mehr sein kann
** f) ** 2 und 4
  * "löst das Rucksackproblem für n Elemente mit O(n^2) zusätzlichem Speicher.": Unsicher, ob man mit dem Algorithmus das Problem lösen kann oder wie die Lösung aussieht. 

** g) ** 2  (achtung, falsch: Folgendes beachten)
  * unsicher
  * Ich denke 4 müsste stimmen
  * Bei 2 bin ich mir auch unsicher, da das eigentlich die Definition des Theta-Kalküls ist (auch ein Landau-Symbol), in den Folien aber steht, dass man mit dem O-Kalkül meistens das meint.
    * Meiner Meinung nach: 3 und 4 sind richtig! Da 1 die definition von gross Omega und 2 von gross Theta ist, wobei die 3 und 4 mit den Rechenregeln des O Kalkuels, bzw 3 bei genauerem Nachdenken ueber den Logarithmus richtig sein muessen. T(n) = T(0.666 * n) = T(c * n) = T(n) + w mit c als Konstante > 1 ist.

==== Aufgabe 2 Streuspeicherung ====

** a) ** Liste
  * 0 E
  * 1 A
  * 2
  * 3 B -> C -> D
  * 4
  * 5
  * 6

** b) ** (P)-> entspricht dem Pfeil mit P und (S) dem Pfeil mit S
  * A 1
  * B 3
  * C 3 (P)-> 4
  * D 3 (P)-> 4 (S)-> 0
  * E 0 (S)-> 1 (P)-> 4 (S)-> 2

==== Aufgabe 3 Binäre Suche ====
[[pruefungen:bachelor:aud:loesungws15:codezuaufgabe3|>>code zum selber testen<<]]

<code java>
<T> int suche(T[] ts, T t, Comparator<T> c1, Comparator<T> c2){
		int a=0, m, z=ts.length -1; //Anfang, Mitte, Ende
		while(z >= a){
			m= (a+z)/2;
			
			if(c1.compare(t, ts[m]) < 0){
				z=m-1;
				
			}else if(c1.compare(t, ts[m]) == 0){
				
				if(c2.compare(t, ts[m]) < 0){
					z=m-1;
				
				}else if(c2.compare(t, ts[m]) == 0){
					return m;
				
				}else{
					a=m+1;
				}
			}else {
				a=m+1;
			}
				
		}
		return -1;
	}
</code>

==== Aufgabe 4 Halden ====
[[https://www.cs.usfca.edu/~galles/visualization/Heap.html|>>>Tool zum selber Testen<<<]]

**a) **Min Heap
  * 0
  * 2 3
  * 7 6 5 4
  * 8 9 10 11 12

**b) **=> Min-Halde
^2|^6|^3|^7|^10|^5|^4|^8|^9|^12|^11|

**c) **=> Min-Halde
^0|^2|^1|^7|^6|^3|^4|^8|^9|^10|^11|^12|^5|

==== Aufgabe 5 Sortieren====
**a)**

^L * ^A1 ^B1 ^F ^A2 ^B2|
|A1|L*|B1|F |A2|B2| 
|A1|B1|L*|F |A2|B2|
|A1|B1|F |L*|A2|B2|
|A1|A2|B1|F |L*|B2|
|A1|A2|B1|B2|F |L*|

**b)**
[[pruefungen:bachelor:aud:loesungws16:codezuaufgabe5|>>code zum selber testen<<]]

<code java>

void sortierenDurchEinfuegen(String[] a) {
	String tmp;
	
	for (int n = 1; n < a.length; n++) {
			
		tmp = a[n]; // entnommenes Element merken
			
			int i = n - 1;
			
		while (i >= 0 && tmp.compareTo(a[i]) < 0) {
			a[i + 1] = a[i];
			i--;
		}

		a[i + 1] = tmp; // entnommenes Element
		// einsetzen
	}
}


</code>
==== Aufgabe 6 Dynamische Programmierung ====
**a)**
  * kaskadenartige

**b)**
 [[https://fsi.cs.fau.de/forum/thread/13920-Summenzeichen-in-Rekursion|Quelle]]
<code java>
long a(int n) {
   if (n <= 1) {
        // Basisfall:
        return 1;
   } else {
        // Rekursion:
        long an = a(n-1);
        for(int i = 1; i < n; i++){
                  an+= a(i)*a(n-i); 
        }
        return an;
  }
}
</code>

**c)**

[[pruefungen:bachelor:aud:loesungws15:codezuaufgabe6|>>>code zum selber testen<<<]]

<code java>
long aDP(int n){
		if(mem == null || n >= mem.length){ 
                                 // Bemerkung: n > mem.length reicht, da mem mit n+1 initialisiert wird
			long[] oldMem=mem;
			mem=new long[n+1];
			
			if(oldMem != null){
				for(int i=0; i < oldMem.length;i++)
				mem[i]=oldMem[i];
			}
			
		}
		
		if(n <= 1){
			mem[n]=1;
		
		}else if(mem[n] == 0){
			
			mem[n]=aDP(n-1);
			
			for(int i=1; i<n; i++)
				mem[n] += aDP(i)*aDP(n-i);
		}
		
		return mem[n];
		
	}
</code>
==== Aufgabe 7 Graphen ====

**a)**
<code java>
void sammle(boolean[][] am, int k, Set<Integer> verb, Set<Integer> bes) {
  if (!bes.contains(k)) {
    verb.add(k);
    bes.add(k);
    for (int i = 0; i < am[k].length; i++) {
        if (am[k][i]) {
            sammle(am, i, verb, bes);
        }
    }

    for (int i = 0; i < am.length; i++) {
        if (am[i][k]) {
            sammle(am, i, verb, bes);
        }
    }
  }
}
</code>

**b)**

<code=java>
List<Set<Integer>> mszt(boolean[][] am) {
		// Ergebnisliste:
		List<Set<Integer>> ergebnis = new LinkedList<>();

		// Menge besuchter Knoten:
		Set<Integer> bk = new HashSet<>();

		// Ermittle alle Teilgraphen mittels Hilfsmethode sammle:
		for (int k = 0; k < am.length; k++) {
			if (!bk.contains(k)) {

				// falls k noch nicht besucht => sammle mit k verbundene Knoten
				Set<Integer> verb = new HashSet();
				sammle(am, k, verb, bk);
				ergebnis.add(verb);

                                //einfacher waere hier statt den letzten drei zeilen folgendes:
                                //sammle(am, k, ergebnis.get(k), bk); 
			}
			
		}
		return ergebnis;
	}
</code>

**c)**

<code=java>
void itg(boolean[][] am, Set<Integer> vs) {
    for (int i = 0; i < am.length; i++) {
        for (int j = 0; j < am.length; j++) {
            if (am[i][j]) {
                if (!vs.contains(i) || !vs.contains(j)) {  // es muss sowohl x als auch y in vs enthalten sein
                    am[i][j] = false; // der Graph ist gerichtet, daher reicht die Betrachtung an einer Stelle
		}
	    }
	}			
    }
}

// alte Loesung:
void itg(boolean[][] am, Set<Integer> vs) {
		for (int i = 0; i < am.length; i++) {
			for (int j = 0; j < am.length; j++) {
				if (am[i][j]) {
					if (!(vs.contains(i) && vs.contains(j))) {
		                                am[i][j] = false;
                                                am[j][i] = false;
					}
				}
			}			
		}
}
</code>

Code zum selber testen:
<code=java>	
public static void main(String[] args){
                //Beispielaufruf mit aus 3 Subgraphen bestehendem Graph
		GraphWS15 g = new GraphWS15();
		boolean[][] am = {{false, true, false, true, false, false},
                                              {false, false, false, true, false, false},
                                              {false, false, false, false, true, false},
                                              {false, true, false, false, false, false},
                                              {false, false, false, false, false, false},
                                              {false, false, false, false, false, false}};
		//Set<Integer> verb = new HashSet();
		List<Set<Integer>> n = g.mszt(am);
		System.out.println(n.size()); 
		System.out.println(n.get(0).size()); 		 
		System.out.println(n.get(1).size()); 
		System.out.println(n.get(2).size()); 
	}
}
</code>

==== Aufgabe 8 ADT ====
<note>TODO</note>

** a) **  
    * collect(Node(g, n)) = add(collect(g), n)  
    * collect(Edge(g, a, b)) = add(add(collect(g), a), b)

** b) **
   * path(Node(g, n), x, y) = path(g, x, y)
   * path(Edge(g, a, b), x, y) =  true      falls (path(g, x, a) ^ path(g, b, y)) v (path(g, y, a) ^ path(g, b, x))   ;  path(g, x, y) sonst

** c) **  
    * isRoot(Edge(g, a, b), x) = isRoot(g,x)    falls x!=b
       false sonst