Übung zur Vorlesung
Grundlegende Algorithmen (WS 03/04)

Leitung:
Jan Griebsch
Zeit und Ort:
Di 16:15 - 17:45, MI 00.04.011
Erster Termin:
28.10.03
Übungszyklus:
Ausgabe der Übungsblätter jeweils Freitags in der Vorlesung; Rückgabe der Lösungen jeweils Freitags am Ende der Vorlesung

gcc unter Windows: gcc ist in dem Softwarepaket cygwin enthalten.
Am Freitag, den 12.12 findet die Rückgabe des Übungsblattes wie gewohnt in der Vorlesung statt.
Blatt 10 Tips
(1) Analog zu Theorem 4.15 aus "grundlegende Algorithmen" von V.Heun.
Idee: Wie baue ich einen Baum der Hoehe h aus 2 kleineren Teilbaeumen auf ?
(2) Der Knoten v muss irgendwie aufgefuellt werden. Was kann man tun, anstatt Knoten zu verschmelzen ? Vielleicht Schluessel migrieren ?
(3) Z.B. konstruieren Sie Graphen (gerne auch induktiv) fuer die unteren/oberen Schranken, bei denen aus dem Konstruktionsprinzip bzw. ihrer Argumentation die Maximalitaet/Minimalitaet der Kantenanzahl hervorgeht.
(4) Ein wirklich gutes Argument duerfte auch ausreichen, eine formale Beweisfuehrung ist nicht unbedingt notwendig.
Am Freitag werde ich nicht in der Vorlesung sein, und Herr Dr. Ernst sehr in Eile, daher muessen Sie ihre Loesung im Lehrstuhl in einen Kasten werfen. Die Korrekturen koennen Sie naechsten Dienstag in der Uebung.
Blatt 10 Korrektur
Der minimale Knotengrad ist natuerlich"a", und nicht "b".

Letzte Änderung: Jan Griebsch am 29.10.2003