• Aufgabe 1
• Aufgabe 6
• Aufgabe 7

a - c)

public class CountingSort {
    public static void sort(char[] in) {
        int[] count = new int[256]; //a)
 
        for(int i = 0; i < in.length; i++) { //b)
            count[in[i]] += 1;
        }
 
        char c = 0; //current char (Teilaufgabe c)
        int index = 0; //write index
        do {
            for(int i = 0; i < count[c]; i++) {
                in[index++] = c;
            }
            c++;
        } while (index < in.length);
    }
}

d) O(n)
e) NEIN, es ist nicht widerlegt, da es sich hier nicht um ein nicht vergleichsbasiertes Sortierverfahren handelt!

a) (A,B) – (B,D) – (B,C)
b) (B,D) – (A,D) – (D,C)
c) NEIN

a)

b)

class HashSet<K>  {
    K[][] map;
    int s, b, c;
 
    HashSet(int s, int b, int c) {
        assert 0 < c && c < s;
        this.s = s; //size of map
        this.b = b; //bucket size
        this.c = c; //collision increment
        map = (K[][]) new Object[s][b];
    }
 
    K put(K k, int hk) {
        assert k != null && 0 <= hk && hk < s;
        int pos = hk; //current position during exploration
        do { //b)
            for(int i = 0; i < b; i++) {
                if(map[pos][i] == null || map[pos][i].equals(k)) { //keine NullPointerException dank lazy evaluation
                    K kold = map[pos][i];
                    map[pos][i] = k;
                    return kold;
                }
            }
            pos = (pos + c) % s;
        } while (pos != hk);
 
        throw new IllegalArgumentException();
    }
}

a)

long b(int n, int m) {
    if(m >= 1 && m <= n-1) {
        return (3*(n-1)*b(n-1,m) + m*b(n-1,m-1))/n;
    } else if((n<m) || (m == 0 && n != 0)) {
        return 0;
    } else if(n == m) {
        return 1;
    } else {
        throw new IllegalArgumentException();
    }
}

b)

long bDP(int n, int m) {
    long[][] mem = new long[n + 1][m + 1];
    for(int i = 0; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            if(j >= 1 && j <= i-1) {
                mem[i][j] = (3*(i-1)*mem[i-1][j] + j*mem[i-1][j-1])/i;
            } else if((i<j) || (j == 0 && i != 0)) {
                mem[i][j] = 0;
            } else if(i == j) {
                mem[i][j] = 1;
            }
        }
    }
    return mem[n][m];
}

a)

axs
    peek(empty) = null
    peek(push(s, n)) = n
    pop(empty) = empty
    pop(push(s,n)) = s

b)

axs
    nat2bin(zero) = push(empty, zero)
    nat2bin(n) = push(nat2bin(div(n, succ(succ(zero)))), mod(n, succ(succ(zero))))

c)

axs
    bin2nat(empty) = zero
    bin2nat(push(S,N)) = add(N,mult(bin2nat(S),succ(succ(zero)))) // (N + 2*bin2nat(S))

a+b)

class DLNode<V> {
    DLNode<V> a; //Referenz auf Vorgänger
    V v; //Aktuelles Element
    DLNode<V> z; //Referenz auf Nachfolger
 
    boolean isDLL() { //Aufgabe (a), checks if this node is part of a Doubly Linked List
        DLNode<V> d = this, c = this.a; //drag/current pointers
        boolean searchedEverything = false;
        while(!searchedEverything) {
            if(!(d.z.a == d && d.a.z == d)) {
                return false;
            }
            d = d.z;
            if(d == this || d == null || (d.z == null && d.a.z == d)) {
                searchedEverything = true;
                break;
            }
        }
        d = this;
        searchedEverything = false;
        while(!searchedEverything) {
            if(!(d.z.a == d && d.a.z == d)) {
                return false;
            }
            d = d.a;
            if(d == this || d == null || (d.a == null && d.z.a == d)) {
                searchedEverything = true;
                break;
            }
        }
 
        return true;
    }
 
    // Andere Lösung, die weniger Vergleiche hat
    // IMHO ist jeweils ein Vergleich in den jeweils ersten IFs in den WHILEs redundant.
    // Außerdem überprüft diese Lösung, ob die DLL auch in beide Richtungen zirkulär ist, wenn sie in eine Richtung zirkulär ist.
 
    boolean isDLL() {
      DLNode<V> d = this, c = this.a;
 
      while (c != this && c != null) {
        if (c.z != d) {
          return false;
        }
        d = c;
        c = c.z; //Anmerkung anderer Student: müsste mMn c = c.a sein
      }
 
      // Anmerkung anderer Student: Das Zuruecksetzen von d fehlt mMn, da man ja unten mit dem oben veraenderten c weitermacht . Hab es mal hier drunter eingefuegt
      d = this; 
 
      DLNode<V> e = this.z;
      while (e != this && e != null) {
        if (e.a != d) {
          return false;
        }
        d = e;
        e = e.a; //Anmerkung anderer Student: müsste mMn e = e.z sein
      }
 
      // Either both null (non-circular) or both not null (circular in both directions!)
      return ((c == null && e == null) || (c != null && e != null));
    }
 
    boolean isLoopedDLL() { //Aufgabe (b), checks if this node is part of a Looped DLL
        DLNode<V> c = this.a;
        if(!isDLL()) {
            return false;
        } else {
            while(c != this) {
                // Zuerst null-Check, c kann hier bereits null sein!
                if(c == null) {
                    return false;
                }
                c = c.a;
            }
            c = this.z;
            while(c != this) {
                if(c == null) {
                    return false;
                }
                c = c.z;
            }
            return true;
        }
    }
}

c+d)

class PriorityDeque<V extends Comparable<V>> {
    DLNode<V> h; //highest prio node (null if empty)
 
    V get(boolean high) { //Aufgabe (c)
        DLNode<V> r = h; //will finally point to requested node
        //list is empty
        if(h == null) {
            throw new NoSuchElementException("[Error] List is empty!");
        }
        //list has only on single node - just empty the deque
        else if(h.a == null || h.a == h) {
            h = null;
        }
        //user requested head - reconfigure internal head pointer
        else if(high) {
            h = h.z;
        }
        //user requested node that preceeds head - retarget r
        else {
            r = h.a;
        }
        //unlink requested node r and return its value
        r.a.z = r.z;
        r.z.a = r.a;
        return r.v;
    }
 
    void put(V v) { //Aufgabe (d)
        DLNode<V> c = h; //current node (drag)
        DLNode<V> n = new DLNode<V>(); n.v = v; n.a = n.z = n;
        if(c == null || c.v.compareTo(v) < 0) {
            //n becomes new head
            h = n;
        } else {
            //search node c that immediately succeeds n
            do {
                c = c.z;
            } while (c.v.compareTo(v) >= 0 && c != h);
        } 
        //insert/link n before c, if c exists
        if(c != null) {
            c.a.z = n;
            n.a = c.a;
            n.z = c;
            c.a = n;
        }
    }
}