19510 V / 19521 Ü Algorithmen und Programmierung III

Zeit

Mo 12-14, Do 14-16

Ort

Takustraße 9, Hörsaal

Dienstag 10-11 oder nach Vereinbarung

Voraussetzungen

Der Stoff von Algorithmen und Programmierung I und II, Programmierkenntnisse in Java und Haskell.

Inhalt

Scheinkriterien

1. 60 % der Gesamtpunktezahl der Übungen
2. Bei jedem Übungszettel bis auf einen müssen mindestens 30 % der Punkte erreicht werden.
3. 50 % der Punkte bei der Zwischenklausur und bei der Abschlussklausur
4. aktive Teilnahme an den wöchentlichen Tutorien und einmaliges Vorrechnen sowie Erstellen einer Musterlösung, nach vorhereiger Einteilung
   

Es werden zwei Klausuren (à 90 oder 120 Minuten) geschrieben. Die erste Klausur in der Mitte des Semesters, am 8. Dezember 2003, (verschoben auf 16. 12.) die zweite am Ende des Semesters. Die zweite Klausur prüft den Stoff, der seit der ersten Klausur vermittelt wurde. Um an den Klausuren teilnehmen zu dürfen, müssen die Kriterien 1 und 2 für die bis zur Klausur bewerteten Übungsblätter erfüllt sein.
Konkret bedeutet Kriterium 1 für die Klausur am 16. 12.: entweder 60% der Punkte der Übungblätter 1-4, oder 60% der Punkte der Übungblätter 1-5.
Für die abschließende Klausur im Februar bedeutet es: entweder 60% der Punkte der Übungblätter 1-11, oder 60% der Punkte der Übungblätter 1-12.

Eine Klausur mit 50% der erreichbaren Punkte (Note 4) oder besser gilt als bestanden. Wer eine Klausur versäumt oder nicht besteht, darf eine Nachklausur am Ende der Wintersemesterferien schreiben. Wer eine Klausur nicht besteht, kann höchstens die Gesamtnote genügend (4) bekommen.

Klausuren

Zeit und Ort der zweiten Teilklausur: Donnerstag, 19. 2. 2004, von 14-16 Uhr (in der Vorlesungszeit). Erlaubt sind alle schriftlichen Unterlagen (auch Bücher), aber natürlich keine technischen Hilfsmittel. Der Stoff der Klausur ist der Vorlesungsstoff ab dem 11.12. und dem 7. Übungsblatt. Zur Berechtigung zur Teilnahme an der Klausur benötigt man entweder 60% der Punkte der Übungblätter 1-11, oder 60% der Punkte der Übungblätter 1-12.

Die Nachklausur zur zweiten Klausur fand am Dienstag, den 6. 4. 2004, von 10-12 Uhr statt.

Für die Nachklausur zur ersten Teilklausur gab es zwei Termine zur Auswahl: Man kann jedoch nur bei einem dieser beiden Termine antreten.

1. in der ersten vorlesungsfreien Woche, und zwar am Donnerstag, den 26. 2. 2004, von 14-16 Uhr im Seminarraum 005.
2. in der letzten vorlesungsfreien Woche, und zwar am Dienstag, den 6. 4. 2004, von 14-16 Uhr im Seminarraum 005.

Übungsblätter, sonstiges Material

• 1. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 30. Oktober 2003
• 2. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 6. November 2003
• 3. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 13. November 2003
• 4. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 20. November 2003
• 5. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 27. November Montag, den 1. Dezember 2003.
  Die Bewertung von Aufgabe 35 wird wie folgt geändert:
  Es gibt 8 Punkte für das Einfügen und Suchen, und 4 freiwillige Zusatzpunkte für das Löschen.
  Wegen der Protestaktionen im Zusammenhang mit dem studentischen Streik wurde der Abgabetermin für das 5. Übungsblatt verschoben, und zwar auf Montag, den 1. Dezember.
  
• 6. Übungsblatt (tex), (ps), (pdf). Abzugeben bis Donnerstag, den 11. Dezember 2003 18. Dezember 2003
  • Postscript-Datei baum.eps zu Aufgabe 40
• 7. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 8. Jänner 2004
• Lösungshinweis zu Aufgabe 44
• 1. Teilkausur (tex), (dvi), (ps), (pdf) vom 16. Dezember 2003
• 8. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 15. Jänner 2004
• 9. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 22. Jänner 2004
  Bei den Exemplaren, die ab 12.1. ausgeteilt wurden, trägt dieses Übungsblatt irrtümlicherweise den Titel "8. Übungsblatt".
•  Java-Programm Menge.java aus der Vorlesung für Mengen mit bis zu 100 Elementen
• 10. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 29. Jänner 2004
• Ersatzklausur zur 1. Teilkausur (tex), (dvi), (ps), (pdf) vom 20. Januar 2004
• 11. Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 5. Feber 2003
• Hinweis zu Aufgabe 66: Die asymptotisch beste Laufzeit erhält man durch Wahl von d ungefähr gleich m/n, aber natürlich mindestens 2.
  
• 12. freiwilliges Übungsblatt (tex), (dvi), (ps), (pdf). Abzugeben bis Donnerstag, den 12. Feber 2003
• 2. Teilkausur (Endklausur) (tex), (dvi), (ps), (pdf) vom 19. Februar 2004
• Nachklausur zur 1. Teilkausur (erster Termin) (tex), (dvi), (ps), (pdf) vom 26. Februar 2004
• Nachklausur zur 1. Teilkausur (zweiter Termin) (tex), (dvi), (ps), (pdf) vom 6. April 2004
• Nachklausur zur 2. Teilkausur (Endklausur) (tex), (dvi), (ps), (pdf) vom 6. April 2004

• Topologisches Sortieren
• Programm TopoSort.java
• Man benötigt für dieses Programm auch die Klasse IntReader.java zum Einlesen ganzer Zahlen
• Heapsort
  • Programm heapsort.java
• Halden
  • Java-Programm Halde.java mit den Klassen PWSchlange.class und Halde.class
• Ereignisgesteuerte Simulation
  • Java-Programm SchiliftSimulation.java
• Backtracking
  • Das 8-Damen-Problem
  • Java-Programm AchtDamen.java
  • Eine Animation (von vielen im Netz) des Bäckträcking-Algorithmus für das Acht-Damen-Problem
  • Haskell-Programm achtdamen.hs
  • Backtracking-Programm HashPaare.java für Aufgabe 23 (Zahlenmengen mit verschiedenen paarweisen Summen)
  • Summenmengen
  • Java-Programm HashPaare.java zum Finden optimaler Summenmengen (Aufgabe 23)
  • Beschreibung einer Konstruktion von Summenmengen mit Intervallänge <8n² (vielleicht nicht wirklich eine "Formel" im Sinne von Aufgabe 27), ohne Erklärung, nach R. C. Bose, "An affine analogue of Singer's theorem", J. Indian Math. Soc., 6 (1942), 1-15.
    
  • Verwandtes Problem: Zahlenmengen mit verschiedenen paarweisen Differenzen, sogenannte Golomb-Maßstäbe
    • M. D. Atkinson, N. Santoro and J. Urrutia, "Integer sets with distinct sums and differences and carrier frequency assignments for nonlinear repeaters", IEEE Transactions on Communications, Com-34 (1986), 614-617.
    • Zyklische Differenzen-Mengen
    • Im Netz verteilte Computersuche nach optimalen Golomb-Maßstäben
      
    • Programme und allgemeine Konstruktionen für gute Golomb-Maßstäbe
• Suchbäume
  • Implementierung von Rot-Schwarz-Bäumen in der Java-Klasse java.util.TreeMap
  • Java-Programm ZweiDreiBaum.java für 2-3-Bäume
• Suchen in Zeichenketten
• Berechnung der Verschiebefunktion, fünfzeiliges Programm mit detailliertem Korrektheitsbeweis