• https://fsi.cs.fau.de/forum/post/159888 Allgemeine Diskussion
• https://fsi.cs.fau.de/forum/post/159926;nocount Aufgabe 3 (Gierige Algorithmen) Schulden begleichen

• 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(n ==0) return 1;
	if(n == 1) return 0;
	if(a[n] == -1){
		a[n]=aDP(n-2, a, b) + 2*bDB(n-1, a, b);
	}
	return a[n];
}
 
long bDP(int n, long[] a, long[] b) {
	if(n ==0) return 0;
	if(n ==1) return 1;
	if(b[n] == -1){
		b[n]=aDP(n-1, a, b) + bDB(n-2, a, b);
	}
	return b[n];
}

• 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];
}

• a)

• b) A → C → E → B

• c)

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);   
 
        //Anmerkung: A ist z.B. Schuldner gegenueber B und D und Geldgeber gegenueber C (s.Zeile 2 S.6)!
    }
    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) {
                S = p;  //(Ergänzt) auch der String des groessten Schuldners muss m.E.n. angepasst werden.
                dS = d;
            }
            if (G == null) {
            G = p;
            dG = d;
            }
            if (dG < d) {
                G = p; //(Ergänzt) auch der String des groessten Geldgebers muss m.E.n. angepasst werden.
                dG = d;
           }
        }
        // begleiche Schuld von S nach G:
        long dmin = Math.min(Math.abs(dS), Math.abs(dG));
        Schuld result = new Schuld (S, dMin, G);
        ergebnis.add(result);
        // aktualisiere deltas von S bzw. G:
        if (dmin == Math.abs(dS)) {
            deltas.put(G, dG - dmin);                   
            deltas.remove(S);
             // Alternative: long dNeuG = deltas.get(G) ;
            // dNeuG += dS; oder  dNeuG -= dmin; 
            // deltas.put(G, dNeuG);
       } else {
            deltas.put(S, dS + dmin);                  
            deltas.remove(G);
             // Alternative: long dNeuS = deltas.get(S);
             // dNeuS += dG; oder  dNeuS += dmin;
             //deltas.put(S, dNeuS);
        }
    }
return ergebnis;
}

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

• a)

Str8ts(boolean[][] blk, int[][] num) { // Konstruktor
    this.blk = blk;
    this.num = num;
    vert = new ArrayList<>();
    horz = new ArrayList<>();
    for(int i = 0; i < 9; i++) {
        vert.add(new HashSet<Integer>());
        horz.add(new HashSet<Integer>());
    }
    // fill vert/horz with predefined values
    for(int row = 0; row < 9; row++) {
        for(int col = 0; col < 9; col++) {
            vert.get(col).add(num[row][col]);
            horz.get(row).add(num[row][col]);
        }
    }
    solve(0, 0); // find solution if possible
}

• b)

boolean isStr8tOrUnfinished(List<Integer> s) {
    Collections.sort(s);
    if (!s.contains(0)) {
        int previous = s.get(0);
 
        for(int i = 1; i < s.size(); i++) {
            if(s.get(i) != previous + 1) {
                return false;
            }
            previous = s.get(i);
        }
    }
    return true;
}

• c)

boolean checkStr8t(int row, int col) {
    List<Integer> sh = new ArrayList<>(), sv = new ArrayList<>();
    int c = col, r = row;
    while (c >= 0 && !blk[row][c]) { // search start of horizontal str8t
        c--;
    } // collect values of current horizontal str8t in sh:
    while(++c < 9 && !blk[row][c]) {
        sh.add(num[row][c]);
    }
    while (r >= 0 && !blk[r][col]) { // search start of vertical str8t
        r--;
    } // collect values of current vertical str8t in sv:
    while(++r < 9 && !blk[r][col]) {
        sv.add(num[r][col]);
    }
    // check that both sh and sv are str8ts or unfinished:
    return isStr8tOrUnfinished(sh) && isStr8tOrUnfinished(sv);
}

• d)

boolean solve(int row, int col) {
    if (row >= 9) {
        return true; // solution found
    } else if (col >= 9) {
        return solve(row + 1, 0);
    } else if (blk[row][col] || num[row][col] > 0) {
        return solve(row, col + 1); // skip field
    }
    for (int v = 1; v <= 9; v++) {
        // if row and column do not contain v...
        if(!vert.get(col).contains(v) && !horz.get(row).contains(v)) {
            // ... process current field:
            num[row][col] = v;
            vert.get(col).add(v);
            horz.get(row).add(v);
 
            // check current str8t and recur on next field:
            if(checkStr8t(row, col)) {
                if(solve(row, col + 1) {
                    return true;
                }
            }
 
            // backtrack current field:
            num[row][col] = 0;
            vert.get(col).remove(v);
            horz.get(row).remove(v);
        }
    }
    return false; // puzzle has no solution
}

• a) 3,4 richtig /–2 recht sicher auch, steht so zumindest auf den TÜ- Folien/ 2 ist falsch, QuickSort kann in-situ implementiert werden siehe Vorlesungsfolie „Überblick über die Sortierverfahren“

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

• c) 1,4 richtig

• d) 1,2 richtig /–Code von 2 in Eclipse eingetippt, hat nicht gemeckert. 3 sollte auch nicht richtig sein, da der rueckgabetyp sehr wohl generisch sein kann, z.b Unimodale Suche

• e) 2 ,3, 4 sind richtig, wobei bei 3 javac -ea fuer „enable assertions“ steht. (Wieso das Stoff in AuD ist, ist fraglich)