===== Forendiskussionen ===== * [[https://fsi.informatik.uni-erlangen.de/forum/thread/12767-klausur-WS2014|Aufgabe 1]] * [[https://fsi.cs.fau.de/forum/thread/12844-WS14-ADT|Aufgabe 6]] * [[https://fsi.cs.fau.de/forum/thread/17211-Mit-this-keyword-auf-Variablen-zugreifen-WS14-Auf|Aufgabe 7]] ===== Lösungsversuch ===== ==== Aufgabe 1 - Wissensfragen (16) ==== ^ Teilaufgabe ^ Lösungsmöglichkeit 1 ^ Lösungsmöglichkeit 2 ^ Lösungsmöglichkeit 3 ^ Lösungsmöglichkeit 4 ^ | a | X | X | | | | b | X | | X | | | c | | | | X | | d | | X | | X | | e | X | | X | | | f | | X | | X | | g | X | X | | | | h | X | | | X | ==== Aufgabe 2 - Sortieren durch Zählen (12) ==== 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! ==== Aufgabe 3 - Prim vs. Kruskal (10) ==== a) (A,B) -- (B,D) -- (B,C)\\ b) (B,D) -- (A,D) -- (D,C)\\ c) NEIN ==== Aufgabe 4 - Streuspeicherung (18) ==== a) ^Bucket -> ^ 0 ^ 1 ^ 2 ^ 3 ^ 4 ^ |1st key | D | A | E | B | | |2nd key | F | | G | C | | b)


class HashSet  {
    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();
    }
}

==== Aufgabe 5 - Dynamische Programmierung (20) ==== 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
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

==== Aufgabe 6 - Abstrakte Datentypen (15) ====
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))


==== Aufgabe 7 - Doppelverkettung (29) ====

a+b) 
class DLNode {
    DLNode a; //Referenz auf Vorgänger
    V v; //Aktuelles Element
    DLNode z; //Referenz auf Nachfolger
    
    boolean isDLL() { //Aufgabe (a), checks if this node is part of a Doubly Linked List
        DLNode 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 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 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 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> {
    DLNode h; //highest prio node (null if empty)
    
    V get(boolean high) { //Aufgabe (c)
        DLNode 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 c = h; //current node (drag)
        DLNode n = new DLNode(); 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;
        }
    }
}