===== Lösungsversuch =====

==== Aufgabe 1 Wissensfragen ====

**a)** 1 und 2

**b)** 2 und 3

**c)** 4

**d)** 2 und 4

**e)** 1

**f)** 1 und 3

**g)** 3 und 4

**h)** 1 und 4

**i)** 1 und 2

**j)** 1 und 3

  * zu 4)
    *=>  Eine endrekursive Methode kann unmittelbar entrekursiviert werden.
   * zu c)
    *=>  Laufzeit ist O(log(n))

==== Aufgabe 2 Suchen und O-Kalkül ====

**a)**
<code java>
static int[] searchNaive(int[] a, int z) {
    int[] r = null;
    for(int i = 0; i < a.length; i++) {
        for(int j = i+1; j < a.length; j++) {
            if(a[i] + a[j] == z) {
                r = new int[] {i, j}; 
            }
        }
    }
    return r;
}
</code>

**b)**
<code java>
static int[] searchLinear(int[] a, int z) {
    int i = 1, j = a.length - 1;
    while(i < j) {
        if(a[i] + a[j] == z) {
            return new int[] {i, j};
        } else if(a[i] + a[j] < z) {
            i++;
        } else {
            j--;
        }
    }
}
</code>

**c)**
<code java>
static LinkedList<Integer> searchDuplicates(int[] a, int[] b) {
    LinkedList<Integer> ds = new LinkedList<>();
    AVLTree at = new AVLTree();
    
    for(int x : a) {
        at.insert(x);
    }
    
    for(int x : b) {
        AVLNode r = at.root;
        
        while(r != null) {
            if(x < r.data) {
                r = r.left;
            } else if(x > r.data) {
                r = r.right;
            } else {
                ds.add(x);
                break;
            }
        }
        
    }
    return ds;
}
</code>

====Aufgabe 3 Bäume ====
**a)**
|    ^ B1 ^ B2 ^ B3 ^
^ Preorder: | ∧∨ab∨cd | ∨∧ab¬∨cd | ∨¬a∧¬b∨¬cd |
^ Inorder: | (a∨b)∧(c∨d)) | a∧b∨¬(c∨d) | ¬a∨¬b∧(¬c∨d) |
^ Postorder: | ab∨cd∨∧ | ab∧cd∨¬∨ | a¬b¬c¬d∨∧∨ |

**b)**
<code java>
LinkedList<KOp> toPrefix() {
    LinkedList<KOp> r = new LinkedList<>();
    
    r.add(o);
    for(KTree c : cs) {
        r.addAll(c.toPrefix());
    }
    
    return r;
}
</code>

<code java>
static KTree fromPostfix(LinkedList<KOp> postfix) {
    Stack<KTree> s = new Stack<>();
    for(KOp o : postfix) {
        switch(o) {
            case AND:
            case OR:
                KTree r = s.pop();
                KTree l = s.pop();
                s.push(new KTree(o, l, r));
                break;
            case NOT:
                s.push(new KTree(o, s.pop()));
                break;
            default:
                s.push(new KTree(o));
        }
    }
    return s.pop();
}
</code>

====Aufgabe 4 Listen ===
**a)**
<code java>
public boolean contains(E e) {
    Node cur = head;
    for(int l = LEVELS - 1; l >= 0; l--) {
        while(cur.next[l] != null && cur.next[l].e.compareTo(e) <= 0) {
            if(cur.next[l].e.compareTo(e) == 0) {
                return true;
            }
            cur = cur.next[l];
        }
    }
    return false;
}
</code>

**b)**
<code java>
private Node[] getPred(E e) {
    Node[] last = (Node []) Array.newInstance(Node.class, LEVELS);
    Node cur = head;
    for(int l = LEVELS - 1; l >= 0; l--) {
        while(cur.next[l] != null && cur.next[l].e.compareTo(e) < 0) {
            cur = cur.next[l];
        }
        last[l] = cur;
    }
    return last;
}
</code>

**c)**
<code java>
public boolean insert(E e) {
    Node newN = new Node(e);
    int newL = getRandomLevel();
    if(contains(e)) {
        return false;
    }
    Node[] pred = getPred(e);
    for(int l = newL; l >= 0; l--) {
        newN.next[l] = pred[l].next[l];
        pred[l].next[l] = newN;
    }
    return true;
}

public boolean delete(E e) {
    if(!contains(e)) {
        return false;
    }
    Node[] pred = getPred(e);
    for(int l = LEVELS - 1; l >= 0; l--) {
        if(pred[l].next[l] != null) {
            pred[l].next[l] = pred[l].next[l].next[l];
        }
    }
    return true;
}
</code>

====Aufgabe 5 ADT====
**a)**

as2gh(Create, Create, k) = Node(New, k)

as2gh(Add(n, ns), as, k) = Edge(as2gh(ns, as, k), k, n)

as2gh(Create, Add(ns, as), k) = Node(as2gh(ns, as, k+1), k)

**b)**

flatten(Add(Create, as)) = flatten(as)

flatten(Add(Add(n, ns), as)) = Add(n, flatten(Add(ns, as)))

**c)**

as2af(as) = as2afh(length(as)+1, as, flatten(as))

as2afh(si, Create, af)) = Add(si, af)

as2afh(si, Add(ns, as), af) = Add(si, as2afh(si+length(ns), as, af))

====Aufgabe 6 Graphen====
**a)**
<code java>
boolean isSafe(boolean g[][], int cs[], int v, int c) {
    for (int n = 0; n < g.length; n++) {
        if (g[v][n] == true && c == cs[n]) {
             // Kante vorhanden und Farbe bereits vergeben
            return false;
        }
    }
    return true;
}
</code>
**b)**
<code java>
boolean helper(boolean g[][], int cs[], int m, int v) {
    // base case
    if (v >= g.length) {
        return true;
    }
    
    // try different colors for vertex v
    for (int c = 1; c <= m; c++) {
        if (isSafe(g, cs, v, c)) {
            int color = cs[v];  // aktuelle Farbe sichern
            cs[v] = c;  // neue Farbe setzen 
            
            if (helper(g, cs, c, v + 1)) { // Rekursion   (Fehler?: sollte m statt c sein)
                return true;
            }
            // backtrack
            cs[v] = color;
        }
    }
    // keine Loesung gefunden -> Schritt zurueck
    return false;
}
</code>

**c)**
<code java>
int[] color(boolean g[][], int m) {
    int[] cs = new int[g.length];
    
    if (!helper(g, cs, m, 0)) {
        return null;
    }
    return cs;
}
</code>