Die Aufgaben sollen in Zweiergruppen bearbeitet werden. Dreiergruppen sind nicht zulässig.
Jede Aufgabe soll  auf einem Extrablatt bearbeitet werden. Bitte auf jedem Blatt Name/Matrikelnummer notieren.
 
 

Aufgabe 27 (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 28 ( 4 + 3 Punkte) dynamisches Hashen
Mit Hilfe der hash-Funktion
                              h: w  ------------>      ( (5*w) +1 ) mod 61
- ein Wert h(w) habe 6 binäre Stellen - sollen die Primzahlen zwischen 200 und 300 (= 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293) abgespeichert werden. Führen Sie sämtliche Einfügeoperationen durch!
Starten Sie mit d=2, d.h. mit einem Feld der Länge 4 für die Seitenadressen. Auf einer Seite sei Platz für 4 Zahlen. (4 Punkte)
Löschen Sie nun alle Primzahlen, die modulo 4 den Rest 1 haben. Verschmelzen Sie ggf. Datenseiten. (3 Punkte)
 
 
Aufgabe 29 (3 + 5 Programmierpunkte) Hashprogramm
Schreiben Sie eine C-Funktion int hmitte(char *text) die zu einer C-Zeichenkette eine Hashadresse zwischen 0 und 1023 liefert. Dabei soll die Methode Mitte des Quadrats verwendet werden. Es sollen jeweils zwei Byte der Zeichenkette als 16-stellige Binärzahl interpretiert werden. Um den gesamten String zu verarbeiten, soll eine Faltungsmethode verwendet werden. Die Hashadresse ist der Rückgabewert der Funktion (3 Punkte)
Zum Testen schreiben Sie eine main() Routine, die Wörter einliest, die zugehörige hash-Adresse berechnet und dort das Wort abspeichert. Implementieren Sie eine Kollisonsstrategie mit Keller und Nachfolgerzeiger für die Kellerelemente.  (5 Punkte)