===== Lösungsversuch Miniklausur WS 2019/20 =====


==== Aufgabe 1 (Wissensfragen) ====
1) 1&2

2) 2&3

3) 3&4


==== Aufgabe 2 (ADT) ====

**a)**

erweitern(p, Leer) = Leer

erweitern(p, Cons(Cons(k, l1), l2)) = Cons(Cons(p,Cons(k,l1),l2))


**b)**

alle(Leer) = Leer

alle(Cons(k, leer)) = Cons(Cons(k,Leer),Leer)

alle(Cons(k, l)) = erweitern(k,alle(l))

**c)**

uHelfer(Leer,ergebnis) = ergebnis

uHelfer(Cons(k,l),ergebnis)= uHelfer(l,Cons(k,ergebnis))



==== Aufgabe 3 (Backtracking) ====


**a)**
<code java>
//counts number of chars in ws
	int countChars(List<String> ws) {
		int cnt = 0;
		if(ws == null) return cnt;
		for(String wort : ws) {
			cnt += wort.length();
		}
		return cnt;
	}
</code>
**b**)
<code java>
        boolean containsAll(List<String> ws) {
		boolean [] chars = new boolean['z' - 'a' + 1];
		int idxOffset = 'a';
		if(ws == null) return false;
		// first pass through ws, toggle all found chars
		for(String wort : ws) {
			for(int i = 0; i< wort.length(); i++) {
				String wortKlein = wort.toLowerCase();
				chars[wortKlein.charAt(i) - idxOffset] = true;
			}
		}
		boolean all = true;
		//second pass: Go through chars array and see if anything still untoggled
		// --> not all chars contained
		for(int i = 0; i < chars.length; i++) {
			if(!chars[i]) return false;
		}
		return all;
	}
</code>
**c)**
<code java>
// helper method : returns null if both null otherwise shorter of two lists
	List<String> better(List<String> a, List<String> b) {
		if(a != null && b != null) {
			int aCnt = countChars(a);
			int bCnt = countChars(b);
			return aCnt <= bCnt? a : b;
		} else if(a == null && b == null) {
			return null;
		} else {
			return a == null ? b : a;
		}
	}

	List<String> getOptimal(List<String> ws) {
                 return helper(ws, 0, new LinkedList<>());
	}

        List<String> helper(List<String> ws, int i, List<String> coll) {
		if(containsAll(coll)) {
			return new LinkedList<>(coll);
		} else if (i < ws.size()){
			List<String> collWith = new LinkedList<>(coll); // clone
			List<String> resWith, resWithout;
			//choose
			String word = ws.get(i);
			collWith.add(word);
			//explore
			resWith = helper(ws, i+1, collWith);
			resWithout = helper(ws, i+1 , coll);
			return better(resWith, resWithout);
		}
		return null;
	}
</code>



==== Aufgabe 4 (Memoization und DP) ====
**a)**
<code java>
	long facMem(int k, long[] fs) {
	        if (k <= 0)
			return 1;
		if (fs[k] > 0)
			return fs[k];
		return k * facMem(k - 1, fs);
	}

	long multiFacMem(int k, int... ks) {
		long div = 1;
		long[] arr = new long[k + 1];
		for (int ki : ks)
			div *= facMem(ki, arr);
		return facMem(k, arr) / div;

	}
</code>

**b)**
<code java>
	List<List<Integer>> powers(int n, int k) {
		List<List<Integer>> all = new ArrayList<>(), part;
		if (n <= 1) {
			List<Integer> last = new ArrayList<>();
			last.add(k);
			all.add(last);
		} else {
			for (int ki = k; ki >= 0; ki--) {
				part = powers(n - 1, k - ki);
				for(List<Integer> l:part) {
					l.add(ki);
				}
				all.addAll(part);
			}
		}
		return all;
	}
</code>