## Lösungsversuch Miniklausur WS 2019/20

### Aufgabe 1 (Wissensfragen)

1) 1&2

2) 2&3

3) 3&4

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)

```//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;
}```

b)

```        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;
}```

c)

```// 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) {
}

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

### Aufgabe 4 (Memoization und DP)

a)

```	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;

}```

b)

```	List<List<Integer>> powers(int n, int k) {
List<List<Integer>> all = new ArrayList<>(), part;
if (n <= 1) {
List<Integer> last = new ArrayList<>();