===== Lösungsversuch =====
==== Aufgabe 1 - Wissensfragen ====
(unsicher) \\
a) 2 und 3 (bei Attributen immer nach statischem Typ) \\
b) 1 und 3\\
c) 1 und 4\\ 

==== Aufgabe 2 - Rekursion ====
<code java>
import java.util.ArrayList;
import java.util.List;

class Ware {
	final String bezeichnung;
	final long preis;

	Ware(String b, long p) {
		this.bezeichnung = b;
		this.preis = p;
	}

}

public class Christkindlesmarkt {

	List<List<Ware>> alle(List<Ware> waren, long geld) {
		List<List<Ware>> llw = new ArrayList<>();

		for (Ware w : waren) {
			 if (w.preis == geld) {
				
				List<Ware> oneProduct = new ArrayList<>();
				oneProduct.add(w);
				llw.add(oneProduct);

			} else if(w.preis> geld){
                           //nichts machen, zu wenig geld
                        } else{
				List<List<Ware>> listRek = alle(waren, geld - w.preis);
				//w noch hinzufuegen 
				for (List<Ware> l : listRek) {
					l.add(w);
				}
				
				llw.addAll(listRek);
			}
		}
		return llw;
	}
}
</code>
==== Aufgabe 3 - Bäume ====
<code>
public class Trie {
    // bis zu 26 Kinder; null, wenn kein Kind mit zugehoerigem Buchstaben:
    Trie[] kind = new Trie[’Z’ - ’A’ + 1];
    String wort; // null, wenn keine Zeichenkette zu speichern ist

void einfuegen(String s) {
         Trie akt = this;
         for (char c : s.toCharArray()) {
             if (c < ’A’ || c > ’Z’) {
                 throw new IllegalArgumentException();
             }
             int zeiger = c - 'A';
             if(akt.kind[zeiger] == null){
                  akt.kind[zeiger] = new Trie();
             }
             
             akt = kind[zeiger]
             
          }
          
          akt.wert = s; 
  }
  
void ausgeben() { // lexikographisch aufsteigend sortiert!
    
    if(this.wort != null){
        System.out.println(this.wort);
    }
    
    for(Trie t : this.kind){
       if(t != null){
          t.ausgeben();
       } 
    }
}
</code>

==== Aufgabe 4 - ADT ====
<code java>
isX(PlayX(t, g), f) :≡ f = g ∧ !isO(t,f) V isX(t,f)

isX(PlayO(t, g), f) :≡ isX(t,f)

tie(t) :≡ all(t) ∧ !winsX(t) ∧ !winsY(t)
</code>