==== Aufgabe 1 ==== a) 1,3,4 //4 ist falsch, nicht die Argumentfolge, sondern die Werte der Terminierungsfunktion müssen streng monoton fallend sein// b) 2,3 //4 ist wahr, mit dem Konzept des Ergebnisse durchreichen lässt sich eine iterative Methode mit Laufzeit O(n) und vier lokalen Variablen (also konstantem Speicherbedarf) schreiben //Anmerkung: Meines Erachtens sollte hier nur 4 richtig sein, da bei 2 zwar der Laufzeitaufwand von O(n) stimmt, aber der Speicheraufwand sollte in O(1) machbar sein, bleibt also die Frage, ob das "benoetigt" hier bedeutet, dass man min. einen Speicheraufwand von O(n) hat. Ausserdem sollte 3 falsch sein, da DP einen Laufzeitaufwand von O(n) hat! c) 2,3,4 Ist 2 nicht die Definition von groß-O? //Ja, 2 ist falsch, 3 ist wahr (das ist literally die Definition von Theta)// d) 1,4 e) 1,2 ==== Aufgabe 2 ==== a) {{:pruefungen:bachelor:aud:avl1.png|}} {{:pruefungen:bachelor:aud:avl2.png|}} b) 31,23,29,19,7,17,13,5,11, 3, 2 c) 41,29,37,23,19,31,13,2,3,5,7,11,17 {{:pruefungen:bachelor:aud:screenshot_2018-07-11_11-24-49.png?300|}} ==== Aufgabe 3 ==== a) int anzahlGutUndDoppelt (int n){ boolean [] b = new boolean[n]; int z = 0; for(int i=0;i b) ist leider nur wenig elegant void naechste(boolean[]b){ boolean carryNew = false, carryOld=true; for(int i=0; i Evtl besser :) void naechste(boolean[]b){ boolean carryNew = false, carryOld=true; for(int i=0; i Evtl noch besser: ^ ist das "Exklusive Oder", wahr wenn genau ein Operand wahr ist, falsch wenn beide Operanden wahr bzw. falsch sind public static void naechste(boolean[] b) { boolean carryNew = false; boolean carryOld = true; for(int i = 0; i < b.length; i++) { carryNew = b[i] && carryOld; b[i] = b[i] ^ carryOld; carryOld = carryNew; } } Evtl noch besserer: for (int i = 0; i < b.length; i++) { b[i] = b[i]? false : true; if(b[i]) break; } c) 2^n long mgl (int n){ return 1 << n; // n Bits nach links shiften } d) int anzahlGute(int n){ int z = 0; boolean[]b = new boolean[n]; long mglk = mgl(n); for(int i=0;i e) ueber(n - 1, k - 1) und ueber(n - 1, k) ==== Aufgabe 4 ==== a) class Cell { List ks; int v; } class Chain { List zs; int sum; boolean satisfiable() { int s = 0; boolean[] vs = new boolean[10]; for(Cell c : zs) { s = s + c.v; vs[c.v] = true; //hier wird die Zahl auf "true" gesetzt if (c.v != 0 && vs[c.v] == true) { // ii) //und hier wird deswegen dann immer false zurueckgegeben return false; } //Loesung vs[c.v] erst nach Abfrage auf "true" setzen //vs[c.v] = true; } if (s > sum && vs[0] == true) { // i) return false; } else if (s != sum && vs[0] == false) { // i) return false; } return true; } b) boolean solve (LinkedList cs) { if (cs.size() <= 0) { return true; } Cell z = cs.removeFirst(); // try to assign 1 to 9 to its v and check all chains that z belongs to for (z.v = 1; z.v <= 9; z.v++) { boolean ok = true; for (Chain c : z.ks) { if (!c.satisfiable()) { ok = false; } } // if all chains are ok => recurse if (ok && solve(cs)) { return true; } } // backtrack z.v = 0; cs.addFirst(z); return false; } ==== Aufgabe 5 ==== class UndirEdge { public final T v, public final T w; UndirEdge(T v, T w) { this.v = v; this.w = w; } } a) Map initUnionFind(List> es) { Map ufds = new HashMap(); for (UndirEdge e: es) { ufds.put(e.v,e.v); ufds.put(e.w,e.w); } return ufds; } b) void union(Map ufds, T v, T w) { ufds.put(v,w); } c) T find(Map ufds, T n) { // find root of n in ufds: while (r != udfs.get(r) { r = udfs.get(r); } // r is now pointing to the root of the partial set tree. // perform path compression: T c = n; pc = ufds.get(c); while (pc != r) { // so lange wir noch nicht bei der Wurzel sind, machen wir die Knoten auf dem Pfad dorthin zu Kindern der Wurzel union(ufds, c, r); c = pc; pc = udfs.get(c); } return r; } ==== Aufgabe 6 ==== a) F(4,F(1,F(2,L(3)))) b) frac2cf(Frac(n, 1)) = L(n) frac2cf(Frac(n, d)) = F(n/d, frac2cf(Frac(d, n%d))) c) cf2frac(L(n)) = Frac(n, 1) cf2frac(F(b, cf)) = Frac(b * num(cf2frac(cf)) + den(cf2frac(cf)), num(cf2frac(cf))) d) same(L(x), L(y)) = x==y same(F(x, a), F(y, b)) = x==y && same(a, b) same(F(x, a),L(y)) = false same(L(x),F(y,b)) = false ==== Aufgabe 7 ==== a) Alpha b) Beta c) Gamma d) 4711 e) Klassenvariable f) öffentlich, überladen g) 16 überlädt 6