Aufgabe 30 (5 Punkte)
In Aufgabe 29 wurde Bucketsort ohne Präprozessing durchgeführt. Überlegen Sie sich ein Beispiel anhand dessen Sie die Vorteile des Präprozessing herausarbeiten können. Führen Sie mit diesen Beispieldaten das Bucketsort durch und zeigen Sie die Stellen, an denen das Präprozessing von Vorteil ist.

 Aufgabe 31 (3+2+2 Punkte)
Es werden 26 Personen zufällig ausgewählt.  Zeigen Sie, daß die Wahrscheinlichkeit, daß es darunter zwei gibt, die am selben Tag Geburtstag haben > 0.5 ist.  Nehmen Sie zur Vereinfachung an, daß alle Geburtstage gleich wahrscheinlich sind, und daß man am 29. Februar nicht auf die Welt kommen kann. (3 Punkte) Ist 26 die kleinste Zahl mit dieser Eigenschaft (2 Punkte). Was ist der Zusammenhang mit dem Stoff der Vorlesung? (2 Punkte)

Aufgabe 32 (3 + 3 Punkte)
Bei mehrdimensionsalen Suchbäumen kann man beim Löschen die Strategie verfolgen benachbarte Hyperrechtecke zu einem neuem  größeren Hyperrechteck zusammenzufassen. Zeigen Sie wie dieser naive Ansatz bereits im dreidimensionalen Fall zu einer Verklemmung (d.h. man findet kein Paar  zum Zusammenfassen) führen kann.  (3 Punkte) Schlagen Sie eine Verbesserung des Algorithmus vor (zusätzliche Anforderung an das Paar, welches verschmolzen wird) und zeigen Sie wie dadurch  das Problem vermieden wird. (3 Punkte)