• https://fsi.cs.fau.de/forum/post/159888

• 1.a)

long aDP(int n) {
    long[] a = new long[n + 1];
    long[] b = new long[n + 1];
    Arrays.fill(a, -1); // -1 == UNKNOWN
    Arrays.fill(b, -1);
    return aDP(n, a, b);
}
 
long aDP(int n, long[] a, long[] b) {
    if(a[n] != -1) {
        return a[n];
    }
    long resultA;
    if(n == 0) { 
        resultA = 1;
    } else if(n == 1) {
        resultA = 0;
    } else {
        resultA = aDP(n-2, a, b) + 2*bDP(n-1, a, b);          //muss hier nicht a[n]=... stehen statt resultA=...
    }
    return resultA;
}
 
long bDP(int n, long[] a, long[] b) {
    if(b[n] != -1) {
    return b[n];
    }
    long resultB;
    if(n == 0 || n == 1) {
        resultB = n;
    }else {
        resultB = aDP(n -1, a, b) + bDP(n-2, a, b);
    }
    return resultB;
}

• 1.b)

long aIter(int n) {
    long[] a = new long[n + 1], b = new long[n + 1];
    a[0] = 1;
    b[0] = 0;
    a[1] = 0;
    b[1] = 1;
    for (int i = 2; i <= n; i++){
        a[i] = a[i-2] + 2*b[i-1];
        b[i] = a[i-1] + b[i-2];
    }
    return a[n];
}

• 2.a)

• 2.b) A → C → E → B
• 2.c)

* 3.

class Schuld {
    final String s; // Schuldner
    final long b; // Betrag
    final String g; // Geldgeber
    public Schuld(String s, long b, String g) { // [s --b--> g] ... }
}

a)

HashMap<String, Long> deltas(List<Schuld> schulden) {
    HashMap<String, Long> ds = new HashMap<>();
    Long dAlt; // altes Delta in ds
    for (Schuld s : schulden) {
        // ausgehender Betrag (von Schuldner):
        dAlt = ds.get(s.s);
        dAlt = dAlt == null ? 0L : dAlt;
        ds.put(s.s, dAlt - s.b);
        // eingehender Betrag (zu Geldgeber):
        dAlt = ds.get(s.g);
        dAlt = dAlt == null ? 0L
                                    : dAlt;
        ds.put(s.g, dAlt + s.b);
    }
    return ds;
}

b)

List<Schuld> minimiere(List<Schuld> schulden) {
    List<Schuld> ergebnis = new LinkedList<>();
    HashMap<String, Long> deltas = deltas(schulden);
    while (deltas.size() > 1) {
        // ermittle groessten Schuldner S bzw. Geldgeber G:
        String S = null, G = null;
        long dS = 0, dG = 0; // Deltas von S bzw. G
        for (String p : deltas.keySet()) {
            long d = deltas.get(p);
            if(S == null) {
            S = p;
            dS = d;
            }
            if (dS > d) { dS = d;}
            if (G == null) {
            G = p;
            dG = d;
            }
            if (dG < d) {dG = d;}
        }
        // begleiche Schuld von S nach G:
        long dmin = Math.min(Math.abs(dS), Math.abs(dG));
        if (deltas.size() == 2){
        Schuld result = new Schuld (S, dMin, G);
        ergebnis.add(result);
        }
        // aktualisiere deltas von S bzw. G:
        if (dmin == Math.abs(dS)) {
            long dNeuG = deltas.get(G) ;
            dNeuG += dS;
            deltas.put(G, dNeuG);
            deltas.remove(S);
       } else {
            long dNeuS = deltas.get(S);
            dNeuS += dG;
            deltas.put(S, dNeuS);
            deltas.remove(G);
        }
    }
return ergebnis;
}

  * 4.a)
           remove(Add(s,v1),v2) = remove (s,v2) falls v1 == v2
                                               Add(remove(s,v2),v1) sonst
 
  * 4.b)
           contains(Add(s, v1), v2) = true falls v1 == v2
                                                  contains(s,v2) sonst
  * 4.c)
           addAll(Add(s1; v); s2) = Add(addAll(s1,s2), v)
  * 4.d)
           eval(Decision(v; t; f); s) = eval (t,s) falls contains(s,v) == true
                                                   eval (f,s) sonst
  * 4.e)
           collect(Decision(v; t; f)) = Add(addAll(collect(t), collect(f)),v)
 
  * 4.f)
           isBDD(Decision(v; t; f)) = isBDD(t)
                                               ^ isBDD(f)  
                                               ^ contains(addAll(collect(t), collect(f)),v)  

• 6.

• a) 3,4 richtig /–2 recht sicher auch, steht so zumindest auf den TÜ- Folien

• b) 2, 3,4 richtig /–4 ist denke ich falsch, siehe 02-2008-7f2.png

• c) 1,4 richtig

• d) 1,3 richtig /–Code von 2 in Eclipse eingetippt, hat nicht gemeckert.

• e) 2 richtig (vielleicht 3 auch richtig, aber nicht sicher)