Department of Computer Science | Institute of Theoretical Computer Science | CADMO

Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

Informatik (D-MATH,D-PHYS) HS13
Theory of Combinatorial Algorithms Institute for Theoretical Computer Science Department of Computer Science ETH Zurich

Informatik für Mathematiker und Physiker (252-0847-00) HS13

Prüfungseinsicht



Die Prüfung vom August 2014 (Basisprüfung) kann an folgenden Daten im CAB G15.2 eingesehen werden:
Prüfungseinsicht nach dem 25. September: Bitte vereinbaren Sie dazu per email einen Termin mit Frau Salow. Mögliche Zeiten sind Mo, Di, Do, Fr 10-12 Uhr sowie 13-15 Uhr im Sekretariat von Frau Salow (CAB G19.1).

Grundlegende Informationen zur Vorlesung

Informationsblatt
Die Bilder zur Lindenmayer Challenge sind da.

Skript

Die Vorlesungsunterlagen für den C++ Teil bestehen aus Skript, Vorlesungsfolien und Übungsunterlagen. Das Skript ist auf Englisch verfasst und wird in einer freien elektronischen Form zur Verfügung gestellt. Die Vorlesungsfolien sind auf Deutsch verfasst und stellen zusammen mit den Übungsblättern den Prüfungsstoff dar. Das heisst, das Skript enthält viele zusätzliche Erklärungen und Übungen.
Sie finden hier auch eine Kurzzusammenfassung zur Vorlesung. Es werden die wichtigsten Konzepte aus jeder Vorlesung aufgeführt und kurz repetiert. Für die Prüfung reicht es aber nicht, nur den Stoff aus der Zusammenfassung zu kennen.

Skript mit Lösungen

Hier finden Sie die Lösungen zu den meisten Aufgaben aus dem Skript. Bedingt durch einig kleine Änderungen im Skript hat sich z.T. die Nummerierung der Aufgaben leicht geändert. D.h. die Aufgabennummern stimmen nicht mehr mit den Aufgabennummern auf den Übungsserien vom Semester überein.

Arbeitsumgebung

In der Vorlesung arbeiten wir für die Programmieraufgaben mit einem Linux-System. Wir stellen Ihnen dafür eine Arbeitsumgebung zur Verfügung, die bereits alles enthält, was Sie brauchen.

Benutzung der Arbeitsumgebung auf einem privaten Computer

Folgen Sie dazu den Anweisungen zur Installation von Linux mit VirtualBox.

Benutzung der Arbeitsumgebung in einem öffentlichen Computerraum, oder für Linux-Experten

Folgen Sie dazu den Anweisungen zur Installation auf Linux.

Testen der Installation

Um ihre Installation zu testen, können Sie versuchen gemäss der Anleitung Kompilieren eigener Programme ihr erstes Programm zu kompilieren und auszuführen.

Übungsserien und Vorlesungsfolien

Damit Sie die Programme auch ausprobieren können, sammeln wir die .cpp Dateien in diesem Ordner. Damit Sie Ihre einen Programme vor der Abgabe selbst testen können, stellen wir im Ordner [Input Data] (zu passenden Serie) einige Beispiele (Eingabe/Ausgabe) zur Verfügung.

Datum Themen Folien / Handout Übungsaufgaben Lösung Programme Videos

Vorlesung 1 (17.09.2013) Mersenne'sche Vermutung, Höhere Programmiersprachen, Editor, Compiler, Computer, Betriebssystem, das erste C++ Programm und seine syntaktischen und semantischen Bestandteile Folien zu den Abschnitten 1.1 bis 2.1 im Skript [PDF] [Aufzeichnung]
Organisatorische Hinweise [PDF]

Ein Artikel aus der Anfangszeit der höheren Programmiersprachen
Serie 1 [PDF] Lösung 1 [PDF] [power8.cpp],
[power8_exact.cpp]
[Mac-Song] [Girls?]

Vorlesung 2 (24.09.2013) Auswertung arithmetischer Ausdrücke, Assoziativität und Präzedenz, arithmetische Operatoren, Wertebereich der Typen int, unsigned int Folien zum Abschnitt 2.2 im Skript [PDF] [Aufzeichnung] Serie 2 [PDF] Lösung 2 [PDF] [fahrenheit.cpp],
[limits.cpp]
[Ariane 5] [Publikums-Reinfall]

Vorlesung 3 (01.10.2013) Boole’sche Funktionen; der Typ bool; logische und relationale Operatoren; Kurzschlussauswertung; Auswahlanweisungen; Iterationsanweisungen; Terminierung; Blöcke, Sprunganweisungen Folien zum Abschnitt 2.3 im Skript [PDF]
Folien zum Abschnitt 2.4 im Skript [PDF] [Aufzeichnung]
Serie 3 [PDF] [Input data] Lösung 3 [PDF] [prime.cpp],
[sum_n.cpp],
[collatz.cpp]
[Marriage Logic]

Vorlesung 4 (08.10.2013) Die Typen float und double; Fliesskommazahlensysteme; Löcher im Wertebereich; IEEE Standard; Grenzen der Fliesskommaarithmetik; Fliesskomma-Richtlinien; Harmonische Zahlen Folien zum Abschnitt 2.5 im Skript [PDF] [Aufzeichnung] Serie 4 [PDF] [Input data] Lösung 4 [PDF] [euler.cpp],
[diff.cpp],
[harmonic.cpp]
[Code Conspiracy], [Infinite Loop]

Vorlesung 5 (15.10.2013) Funktionsdefinitionen- und Aufrufe, Vor- und Nachbedingungen, Assertions, Gültigkeitsbereich, Bibliotheken, Standardfunktionen Folien zum Abschnitt 2.6 im Skript [PDF] [Aufzeichnung] Serie 5 [PDF] [Input data] Lösung 5 [PDF] [callpow.cpp],
[callpow2.cpp],
[callpow3.cpp],
[callpow4.cpp],
[pow.cpp], [pow.h],
[prime2.cpp]
[C64-Intro]

Vorlesung 6 (22.10.2013) Feldtypen, Sieb des Eratosthenes, Speicherlayout, Iteration, Vektoren, Zeichen, Texte, Caesar-Code, String Matching, Mehrdimensionale Felder, Vektoren von Vektoren, Kürzeste Wege Folien zum Abschnitt 2.7 im Skript [PDF] [Aufzeichnung] Serie 6 [PDF] [Input data] Lösung 6 [PDF] [eratosthenes.cpp],
[eratosthenes2.cpp],
[caesar_encrypt.cpp],
[caesar_decrypt.cpp],
[string_matching.cpp],
[string_matching2.cpp],
[shortest_path.cpp]
[Eratosthenes],
[QBasic-Nerd]

Vorlesung 7 (29.10.2013) Felder als Funktionsargumente, Zeiger, Iteratoren auf Vektoren, Container Folien zum Abschnitt 2.8 im Skript [PDF] [Aufzeichnung] Serie 7 [PDF] [Input data] Lösung 7 [PDF] [fill.cpp],
[fill2.cpp],
[fill3.cpp],
[fill4.cpp],
[fill5.cpp],
[fill6.cpp],
[vector_iterators.cpp]
[PathFinder],
[Kürzeste Wege Animation]

Vorlesung 8 (05.11.2013) Rekursive Funktionen, Korrektheit, Terminierung, Rekursion vs. Iteration Folien zum Abschnitt 2.9 im Skript (Teil 1) [PDF] [Aufzeichnung] Serie 8 [PDF] [Input data] Lösung 8 [PDF] [Xerox Alto],
[Patrick]

Vorlesung 9 (12.11.2013) Sortieren mit Merge-Sort, Fraktale, zeichnen mit Lindenmayer-Systemen Folien zum Abschnitt 2.9 im Skript (Teil 2) [PDF] [Aufzeichnung] Serie 9 [PDF] [Input data] Lösung 9 [PDF] [merge_sort.cpp],
[dragon.cpp],
[snowflake.cpp]
[Obama]

Vorlesung 10 (19.11.2013) Rationale Zahlen, Struct-Definition, Referenztypen, Operator-Überladung, Temporäre Objekte, Const-Referenzen Folien zu den Abschnitten 3.1-3.2 im Skript [PDF] [Aufzeichnung] Serie 10 [PDF] [Input data] Lösung 10 [PDF] [userational.cpp],
[userational2.cpp],
[rational.cpp]
[Complex]

Vorlesung 11 (26.11.2013) Datenkapselung, Klassen-Typen, Mitgliedsfunktionen, Konstruktoren, Konversionen, Zufallszahlen Folien zum Abschnitt 3.3 im Skript [PDF] [Aufzeichnung] Serie 11 [PDF] [Input data] Lösung 11 [PDF] [choosing_numbers.cpp] [A million random digits]

Vorlesung 12 (03.12.2013) Listen, Dynamischer Speicher, Funktionalität, Copy-Konstruktor, Zuweisungsoperator, Destruktor, Konzept Dynamischer Datentyp Folien zum Abschnitt 3.4 im Skript [PDF] [Aufzeichnung] Serie 12 [PDF] [Input data] Lösung 12 [PDF] [list.cpp],
[list.h],
[node.cpp],
[node.h]
[Pointer fun] [New and delete]

Vorlesung 13 (10.12.2013) Mengen, Funktionalität, Binäre Suchbäume, Heaps, Treaps Folien [PDF] [Aufzeichnung] Serie 13 [PDF] [Input data] Lösung 13 [PDF] [Treap.cpp],
[Treap.h],
[TreapNode.cpp],
[TreapNode.h],
[treapSort.cpp],
[treapShow.cpp],
[treapTest.cpp]

Probeklausur (17.12.2013) Kurzzusammenfassung zur Vorlesung [PDF] Es finden keine Übungen statt.


Videoaufzeichnung

Die Vorlesung wird in diesem Semerster auf Video aufgezeichnet. Sie finden die Aufzeichnungen auf dem Multimedia Portal. Sie können die Aufzeichnungen auch als RSS Feed oder in iTunes abonnieren.

Termine

Vorlesung: Dienstag 13:15-15:00, ML D28 und ML E12 (Videoübertragung).
Bernd Gärtner CAB G 31.1, Tel: 044 632 70 26, gaertner@inf.ethz.ch.
Übung: Dienstag 15:15-17:00
Chefassistent: Sebastian Stich CAB G 39.3, Tel: 044 632 43 29, sstich@inf.ethz.ch.

Die Einteilung in die Übungsgruppen wird in der ersten Vorlesung vorgenommen. Wenn Sie in dieser Stunde nicht anwesend sein können, wenden Sie sich per Email an Sebastian Stich (sstich@inf.ethz.ch) zwecks nachträglicher Einteilung.
GruppeRaumAssistentInEmail
A CAB G56 Florian Andritsch floriana@ethz.ch
B CHN D44 Liat Ben-Haim lbenhaim@ethz.ch
C CAB G59 Lucas Brutschy lucas.brutschy@inf.ethz.ch
D HG D5.1 Roman Cattaneo romanc@student.ethz.ch
E CHN D48 Cristina Basescu cba@inf.ethz.ch
F CHN G22 Dimitar Dimitrov dimitar.dimitrov@inf.ethz.ch
G HG D1.2 Milos Novaceck milos.novacek@inf.ethz.ch
H HG F26.3 Antonis Thomas athomas@inf.ethz.ch
I ML H41.1 Daniele Spampinato daniele.spampinato@inf.ethz.ch
J HG D3.3 Jannick Griner grinerj@ethz.ch
K LFW E13 Sezer Güler guelerse@student.ethz.ch
L HG D5.3 Carsten Heinrich carstenl.heinrich@gmx.net
M HG F26.5 Christoph Müller muellch@student.ethz.ch
N CHN E42 Georg Ofenbeck ofenbeck@inf.ethz.ch
O IFW A34 Martina Seps sepsma@student.ethz.ch
P LFW E11 Lukas Vogel luvogel@student.ethz.ch
Q CAB G57 Michel Werder werdemic@student.ethz.ch
R ML J37.1 Christian Wieser chwieser@student.ethz.ch
S ML J34.1 Christian Zingg zinggch@student.ethz.ch
T NO D11 Patrick Zöchbauer patrickz@student.ethz.ch

Die Gruppen E-H werden auf Englisch gehalten. Die Gruppe I wird auf Italienisch gehalten.

Inhalt der Vorlesung

Der Hauptteil der Vorlesung ist eine algorithmisch orientierte Einführung ins Programmieren anhand der Sprache C++. Dieser Teil gliedert sich in die drei Bereiche "Grundlagen", "Funktionen" und "Klassen". Besonderes Augenmerk liegt auf dem Rechnen mit arithmetischen Typen.

Hinweise zur Übung

Auf jeder Übungsserie gibt es mehrere Aufgaben, die schriftlich zu bearbeiten und zum angegebenen Termin abzugeben sind. Programmieraufgaben senden sie bis zu diesem Termin per E-Mail an den Übungsleiter ihrer Übungsgruppe.

Prüfung

Die Prüfung besteht aus einer zweistündigen Klausur. Es sind keine Hilfsmittel erlaubt.

Die Referenz für den Prüfungsstoff ist alles, was in der Vorlesung besprochen wurde, die Übungsaufgaben und der Inhalt der Probeprüfung. Insbesondere bedeutet das, dass zusätzliche Informationen aus dem Skript nicht an der Prüfung verlangt werden.

Probeprüfung

In der letzten Vorlesungsstunde (17.12.2013) findet eine freiwillige Probeprüfung statt. Geprüft wird der Stoff aus dem ganzen Semester. Bei Studenten, die in der Probeprüfung eine bessere Note erzielen als in der Hauptprüfung im Januar/Februar 2014 oder August 2014, wird die Endnote (Resultat in der Hauptprüfung) um eine Viertelnote (0.25) aufgerundet. Bei gleich gutem oder schlechterem Abschneiden in der Probeprüfung wird die Endnote nicht verändert.
Anmeldung: Wenn Sie nicht in die aktuelle Vorlesung eingeschrieben sind, aber im Januar/Februar 2014 oder August 2014 die Prüfung ablegen, können Sie die freiwillie Probeprüfung auch schreiben. Melden Sie sich dazu vorgägig bitte per Email bei Sebastian Stich (sstich@inf.ethz.ch).

Repetitionsprüfung

In der Repetitionsprüfung wird der Stoff der zuletzt gelesenen Vorlesung geprüft. Für die Repetitionsprüfung im Januar/Februar 2014 ist also der Stoff von diesem Semester (HS13) massgebend. Insbesondere bedeutet dies auch, dass die Probeklausur vom Dezember 2013 angerechnet werden kann.

Alte Prüfungen

Als Vorbereitung auf die Prüfung stellen wir Ihnen hier eine Liste alter Prüfungen und Musterlösungen zu dieser Vorlesung zur Verfügung. Angaben in den Lösungen ohne Gewähr. Wir empfehlen Ihnen, die Klausuren zunächst ohne Ansicht der Lösung zu bearbeiten und erst danach eine Selbstkontrolle mit Hilfe der Lösungen vozunehmen.
  1. Klausur Frühjahr 2014 (English) und die Lösung dazu.
  2. Probeklausur A Dezember 2013 (English) und die Lösung dazu.
    Probeklausur B Dezember 2013 (English) und die Lösung dazu.
  3. Klausur Herbst 2013 (English) und die Lösung dazu.
  4. Klausur Frühjahr 2013 und die Lösung dazu.
  5. Klausur Herbst 2012 und die Lösung dazu.
  6. Klausur Frühjahr 2012 und die Lösung dazu.
  7. Klausur Herbst 2011 und die Lösung dazu.
  8. Klausur Frühjahr 2011 und die Lösung dazu.
  9. Klausur Herbst 2010 und die Lösung dazu.
  10. Klausur Frühjahr 2010 und die Lösung dazu.
  11. Klausur Herbst 2009 und die Lösung dazu.
  12. Klausur Frühjahr 2009 und die Lösung dazu.
  13. Klausur Herbst 2008 und die Lösung dazu.
  14. Klausur Frühjahr 2008 und die Lösung dazu.
  15. Klausur Herbst 2007 und die Lösung dazu.
  16. Klausur Herbst 2006 und die Lösung dazu.
  17. Klausur Frühjahr 2006 und die Lösung dazu.
  18. Klausur Herbst 2005 und die Lösung dazu.

Literatur und Links



Last modified: , by Bernd Gärtner. Valid HTML 4.0! Valid CSS!