===== Forendiskussionen ===== * [[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 ===== Lösungsversuch ===== ==== Aufgabe 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(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];
}

==== Aufgabe 2 ==== * a) ^ A ^ B ^ C ^ D ^ E ^ Prio-Queue ^ | 0 | ∞ | ∞ | ∞ | ∞ | [A] | | 0 | 15 | 5 | ∞ | 12 | [C, E, B] | | 0 | 13 | 5 | 10 | 8 | [E, D, B] | | 0 | 10 | 5 | 9 | 8 | [D, B] | | 0 | 10 | 5 | 9 | 8 | [B] | |Endergebnis ||||| | 0 | 10 | 5 | 9 | 8 | [ ] | * b) A -> C -> E -> B * c) ^ uj ^ vi ^ wk ^ γj,k alt ^ γj,i,k ^ γj,k neu ^ |A| C |B| 15 | 13 | 13 | |A |C| D | ∞ | 10|10| |A |C |E|12|8|8| |A|D |B|13|12|12| |C |D |B|8|7|7| |E |D |B|2|3|2| |A| E |B|12|10|10| |A| E |D|10|9|9| |C |E |B|7|5|5| |C |E |D|5|4|4| ==== Aufgabe 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 deltas(List schulden) {
    HashMap 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 minimiere(List schulden) {
    List ergebnis = new LinkedList<>();
    HashMap 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;
}

==== Aufgabe 4 ====


  * 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)

==== Aufgabe 5 ==== * 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());
        horz.add(new HashSet());
    }
    // 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 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 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
}

==== Aufgabe 6 ==== * 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 {{:pruefungen:bachelor:aud:02-2008-7f2.png?linkonly|}} * 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)