===== Lösungsversuch SS 19 =====
====   Aufgabe 1 (Wissensfragen)====
=== a) ===
  - Falsch, der gierige Algorithmus findet 25,10,5 was 40 ergibt
  - Richtig
  - Richtig
  - Falsch, Horner Schema ist iterativ möglich

=== b) ===
  - Richtig
  - Falsch 
  - Falsch
  - Falsch

=== c) ===
  - Richtig
  - Falsch 
  - Falsch 
  - Richtig

=== d) ===
  - Richtig, offene Adressierung ist z.B. lineares Sondieren
  - Richtig, O(log(n)) wenn contains mit binärerSuche sucht
  - Falsch, O(n)
  - falsch, andersrum 


=== e) ===
  - Richtig, die anzahl der Bänder verändert die Laufzeit nicht
  - Richtig, auch wenn Θ(n2) und nicht O(n2) angegeben ist, müsste das stimmen 
  - Falsch, man brauch 50 Fächer
  - Falsch, Verallgemeinertes Sortieren = Radixsort. Radixsort hat eine Laufzeit von O(n*k), Bucketsort hat O(n+K)  

=== f) ===
  - Richtig
  - Richtig
  - Falsch, man muss ja trotzdem die Knoten mit in Betracht ziehen 
  - Falsch, Dijkstra bestimmt nicht den minimalen Spannbaum, sondern die küzesten Wege

=== g) ===
  - Richtig, Skript 15, Seite 15
  - Richtig
  - Falsch, immer O(n²)
  - Falsch, Definition für zerteilen / divisiv 

====   Aufgabe 2 (Dynamische Programmierung)====

=== a) ===
 verschachtelte Rekursion

=== b) ===

<code=java>
public static int g(int n) {
		if (n == 1)
			return 1;
		return 1 + g(n - g(g(n - 1)));
	}
}
</code>
=== c) ===

<code=java>
    public static int gMem(int n) {
		assert n >= 1;
		return gMH(n, new int[n + 1]); // m[0] is left unused

	}

	public static int gMH(int n, int[] m) {
		assert n >= 1;
		if (n <= 1) {
			return 1;
		} else if (m[n] == 0) {
			m[n] = 1 + gMH(n - gMH(gMH(n - 1, m), m), m);
		} else {
			return m[n];
		}
		
		return m[n];
	}
</code>

=== d) ===

<code=java>
     static int gDP(int n) {
		assert n >= 1;
		int[] m = new int[n + 1]; // m[0] is left unused
		m[1] = 1;
		for (int k = 2; k <= n; k++) {
			m[k] = 1 + m[k - m[m[k - 1]]];
		}
		
		return m[n];
	}
   
</code>

====   Aufgabe 3 (Bäume)====
=== a) ===
  * 7 einfügen: 8,6,10,4,7,null,12
  * 11 einfügen: 10,8,12,4,null,11,14
  * 5 einfügen: 8,5,10,4,6,null,null

=== b) ===
1,2,6,8,4,12,14,16,19,10

=== c) ===
4,12,6,14,16,10,8,22,20,18

=== d) ===
  * preorder: 2,4,8,10,6,12,14
  * inorder: 8,4,10,2,12,6,14
  * postorder: 8,10,4,12,14,6,2

=== e) ===
  * DFS: 0,1,4,5,2,7,6,3,8 (diese Reihenfolge entsteht nur, wenn man in die Stack immer den hösten Wert der Nachfolger zu erst einfügt, so ist sicher gestellt, dass man das niedrigste Kind als erstes von dem aktuellen Knoten besucht) 
  * BFS: 0,1,2,3,4,5,7,8,6 (hier wird immer das kleinste Kind in die Queue eingefügt um so sicherzugehen, dass man zuerst kleine kinder besucht) 


====   Aufgabe 4 (Maximale Teilsummen in Listen mit Sortierung)====
=== a,b,c,d im unteren Code ===
<code=java>

public class Aufgabe3 {

	public static void main(String[] args) {
		LinkedList<Integer> l1 = new LinkedList<Integer>(Arrays.asList(2, 3, 30, 90, 120, 240, 511));
		LinkedList<Integer> l2 = new LinkedList<Integer>(Arrays.asList(1, 3, 12, 32, 90, 125, 240));
		List<Integer> e = maxPartSumList(l1, l2);
		System.out.println(e);
	}

	// a
	static List<Integer> subListHead(List<Integer> one, int lastIndex) {

		// falls LastIndex letzter Eintrag ist draf man nicht mit +1 die Liste erstellen
		return (lastIndex < one.size() ? one.subList(0, lastIndex + 1) : one.subList(0, lastIndex));

	}

	// returns the values from ’one’ starting immediately after lastIndex
	static List<Integer> subListTail(List<Integer> one, int lastIndex) {
		return one.subList(lastIndex + 1, one.size());
	}

	// b
	private static int partSum(List<Integer> part) {
		int r = 0;
		for (int i : part) {
			r += i;
		}
		return r;
	}

	// c
	private static List<List<Integer>> split(List<Integer> one, List<Integer> two) {

		List<List<Integer>> r = new LinkedList<>();
		for (int v : two) {
			int idx = one.indexOf(v);
			if (idx != -1) {
				r.add(subListHead(one, idx));
				List<Integer> neu = subListTail(one, idx);
				one = new LinkedList<>(neu);
			}
		}
		// falls one groesser two, ist one noch nicht komplett leer und muss noch an r
		// angefügt werden
		if (!one.isEmpty()) {
			r.add(one);
		}
		return r;
	}

	// d
	private static List<Integer> maxPartSumList(List<Integer> one, List<Integer> two) {
		List<Integer> r = new LinkedList<>(), oneP, twoP;
		Iterator<List<Integer>> oneI = split(one, two).iterator();
		Iterator<List<Integer>> twoI = split(two, one).iterator();

		while (oneI.hasNext() && twoI.hasNext()) {
			// wichtig .next nur einmal in while schleife aufrufen,
			// da mit jedem .next der Iterator eins weiter geht!!!
			List<Integer> eins = oneI.next();
			List<Integer> zwei = twoI.next();
			int sumOne = partSum(eins);
			int sumTwo = partSum(zwei);
			if (sumOne >= sumTwo) {

				r.addAll(eins);
			} else {

				r.addAll(zwei);
			}
		}

		// falls noch letzter Abschnitt hinzugefügt werden muss
		if (oneI.hasNext()) {
			r.addAll(oneI.next());
		}
		if (twoI.hasNext()) {
			r.addAll(twoI.next());
		}

		return r;
	}

}

</code>

====   Aufgabe 5 (Graph-Algorithmen)====

=== a) ===
<code=java>
boolean isStronglyConnected(Graph<E> g) {
		Set<E> allNodes = g.allNodes();
		for (E start : allNodes) {
			LinkedList<E> visited = new LinkedList<>(), queue = new LinkedList<>();
			queue.add(start);
			while (!queue.isEmpty()) {
				E akt = queue.poll();
				// wenn aktueller Knoten quelle ist dann kein zusamenhängender Graph
				if (preds(akt).isEmpty()) {
					return false;
				}
				if (!visited.contains(akt)) {
					visited.add(akt);
					List<E> nachfolger = succs(akt);
					if (nachfolger.isEmpty()) {
						// aktueller Knoten ist Senke, kann kein stark zusammenhängeder graph sein
						return false;
					}
					for (E i : nachfolger) {
						queue.add(i);
					}

				}//visitedAbfrage schließt
			}//while schießt
             if(visited.size()!=allNodes.size()){
                  return false; // abfrage ist wichtig, weil es kann sein, dass zwei Knoten gegenseitig auf sich zeigen, damit haben sie beide Vor und Nachfolger aber die anderen Knoten werden nicht erreicht 
		}	
		}//forschleife schließt
		return true;
	}
</code>

=== b) ===
<code=java>
boolean hasEulerCircuit(Graph<E> g) {
		Set<E> allNodes = g.allNodes();
		for(E akt : allNodes) {
			List<E> vor = preds(akt);
			List<E> nach = succs(akt);
			if(vor.size() != nach.size()) {
				return false;
			}
		}
		return isStronglyConnected(g);
	}
</code>

=== c) ===
<code=java>
List<E> euler(Graph<E> g, E node) {
		LinkedList<E> stack = new LinkedList<>(), euler = new LinkedList<>();
		stack.add(node);
		while(!stack.isEmpty()) {
			E akt = stack.peek(); //nicht rauslöschen!!!  
			List<E> nach = succs(akt);
			if(nach.isEmpty()) {
				//keine nachfolger = Blattknoten -> zu Euler hinzu
				euler.addFirst(akt); //vorne anfügen
                                stack.pop();
			}else {
				for(E e : nach) {
					stack.push(e);
				}
				//besuchte Kante löschen
				g.removeEdge(akt,stack.peek());
			}
		}
		return euler;
	}
</code>

====   Aufgabe 6 (Abstrakte Datentypen)====

=== a) ===
<code=java>
Union(Empty,s2) = s2
Union(add(s2,e),s2)= Add(unision(s1,s2),e)
</code>

=== b) ===
<code=java>
ContainsAll(s1,Empty) = true 
containsAll(Empty,s2) = false 
containsAll(s1,Add(s2,e)) = ContainsAll(s1,s2) && contains (s1,e)
</code>

=== c) ===
<code=java>
costSum(Create) = 0
CostSum(Append(l,s,c)) = c+costsum(l) 

</code>
=== d) ===
<code=java>
setUnion(Create) = Empty
setUnion(Append(l,s,c)) = union(S,setUnion(l))
</code>

=== f) ===
<code=java>
sCH(Create, u, accu) = ...
... accu falls containsAll (setUnion(accu), u)
... create sonst

sCH(Append(l,s,c),u,accu= ...
... sCH(l,u,better(Append(accu,s,c),accu))
</code>
____________________________________________________________________
====   Aufgabe 7 (Backtracking)====
=== a) ===
<code=java>
String getVerticalPrefix(int r, int c) {
		
		if(r<0 || g[r][c]=='#' || r>= g.length || c >= g[r].length) {
			return "";
		}else {
			return g[r][c]+getVerticalPrefix(r-1,c);
		}
	}
</code>

=== b) ===
<code=java>
List<String> consumeV(int r, int c, String w) {
		List<String> wsPV = new LinkedList<>(); // completed by inserting w
		for (int i = c; i < c + w.length(); i++) {
			String vp = getVerticalPrefix(r,i);
			if(wsV.contains(vp)) {
				wsV.remove(vp);
				wsPV.add(vp);
			}
		}
		return wsPV;
	}
</code>
=== c) ===
<code=java>
boolean solve() {
		return helper(0, 0); // will always return true
		}
		boolean helper(int r, int c) {
		// traverse g row by row and left to right
			if(wsH.isEmpty()) {
				return true; 
			} else if(c>g[r].length) { // ende der Zeile
				return helper(r+1,0);
			}else if(g[r][c] =='#') { //worttrenner
				return helper(r,c+1);
			}
			
			// try placing each remaining w from wsH at g[r][c]
			boolean[] cpH; // result from placeH
			List<String> wsPV; // result from consumeV
			for (int i = 0; i < wsH.size(); i++) {
				String w = wsH.remove(i);
				
				if(canPlace(r,c,w)) {
					cpH = placeH(r,c,w);
					wsPV = consumeV(r,c,w);
					if(helper(r,c+w.length())) {
						return true;
					}
					//keine Lösung, backtrack
					unPlace(r,c,cpH);
					wsV.addAll(wsPV); // consume loescht das Wort in wsV und speichert es in wsPV, das muss zurückkoppiert werden
					wsH.add(w);
			}
			
		}
		return false;
	}
</code>