Database Research Group

WSI – Database Systems Research Group

Selected Fun Problems of the ACM Programming Contest (Proseminar)


News
  • Oct 13, 2021 — Corona: Anmeldung zur Teilnahme an Präsenzlehrveranstaltungen

    Der Vorbesprechungstermin für dieses Seminar findet am 22. Oktober im Raum B305.1 auf dem Sand 13 um 12:00 Uhr statt. Um am Vorbesprechungstermin teilnehmen zu können, ist eine vorherige Anmeldung verpflichtend. Die Anmeldung erfolgt über einen Ilias-Kurs:

    Anmeldung zur Vorbesprechung

    Nachweis von 3G

    Für alle Präsenzlehrveranstaltungen gilt 3G, das heißt, an einer solchen Lehrveranstaltung darf nur teilnehmen, wer geimpft, genesen oder negativ auf Covid-19 getestet ist. Personen, die nicht geimpft und nicht genesen sind, können durch einen negativen Antigen-Schnelltest oder einen negativen PCR-Test nachweisen, dass sie nicht an Covid-19 erkrankt sind. Die entsprechenden Testergebnisse von Antigen-Schnelltests müssen tagesaktuell sein, das heißt, der Test darf zum Zeitpunkt der Lehrveranstaltung maximal 24 Stunden zurückliegen; PCR-Tests dürfen nicht älter als 48 Stunden sein.

    Bitte habt immer folgendes dabei:

    • Eine medizinische Maske, die ihr während des Seminars tragt, sofern ihr von den Sitznachbarn nicht mindestens 1,5 m Abstand halten könnt.
    • Einen Nachweis zur Einhaltung der 3G-Regeln, also:
      - einen Impfnachweis (per Corona-Warn- bzw. CovPass-App o.ä.) oder
      - ein negatives Testergebnis eines Antigen-Schnelltest (nicht älter als 24 Stunden) bzw. einen negativen PCR-Test (nicht älter als 48 Stunden) oder
      - einen Nachweis dafür, dass ihr von CoViD19 genesen seid.

    Diese Vorgaben sind eine Kurzfassung der Richtlinien der Universität, die ihr hier im Detail nachlesen könnt: SARS-CoV-2 Hinweise für Studierende
    Denis Hirn


In diesem Proseminar werden die TeilnehmerInnen mit jeweils einem ausgewählten Problem des seit 1970 alljährlich stattfindenden ACM Programming Contest konfrontiert. Diese Probleme zeichnen sich einerseits durch recht spassige und interessante Aufgabenstellungen aus, andererseits erlauben diese Aufgaben Lösungen, die oft sehr elegant und kompakt sind (der Kern umfasst typischerweise weniger als 50 Zeilen Programmcode) und fast immer mit “Aha!”-Effekten einhergehen.

Die SeminarteilnehmerInnen werden jeweils das Problem vorstellen, eine möglichst elegante Lösung—formuliert in der Lieblingsprogrammiersprache der Teilnehmerin—erarbeiten und diese während des Seminarvortrags präsentieren. (Falls es bei der Lösung des Problems "haken" sollte, ist das kein Show Stopper: wir geben dazu gerne Tipps — niemand muss deshalb dieses Seminar nicht bestehen.)

Anmeldung zum Seminar und Termine

⚠️ Der Vorbesprechungstermin für dieses Seminar findet am 22. Oktober im Raum B305.1 auf dem Sand 13 um 12:00 Uhr statt. Um am Vorbesprechungstermin teilnehmen zu können, ist eine vorherige Anmeldung verpflichtend. Die Anmeldung erfolgt über einen Ilias-Kurs:

Anmeldung zur Vorbesprechung

Die Anmeldung zum Seminar werden wir direkt im Anschluss an diesen Termin vor Ort durchführen.

Die Termine der Vorträge selbst sprechen wir mit euch ab, sobald der genaue Kreis der Studierenden feststeht. Wir finden sicher Termine, die in eure Kalender passen.

Ansonsten gilt im Laufe des Semesters für alle Teilnehmer, an allen Terminen anwesend zu sein! Weitere interessierte Hörer sind herzlich willkommen.

Themen (ACM ICPC Problemstellungen) und Seminarablauf

Eine Einführung in das Seminar, ein Blick auf beispielhafte Problemstellungen und die Themenvergabe finden in einem ersten Treffen zu Beginn des Semesters statt.

Je zwei eurer Vorträge (Länge je ca. 25-30 Minuten, mit anschliessender kurzer Diskussion) werden zu den Seminarterminen stattfinden. Die Termine legen wir in Absprache mit euch fest.

Es besteht eine Verpflichtung zur Anwesenheit an allen Terminen — nicht zuletzt schon aus Fairness gegenüber euren Kommilitonen. Gebt uns ggf. Bescheid, falls ihr zu einem Termin begründet nicht erscheinen könnt.

Im Folgenden findet ihr einige ACM ICPC Problems als Beispiele für Probleme, die wir in diesem Seminar bearbeiten wollen:

ACM ICPC Problems:

Zu einigen der Probleme, die wir bearbeiten werden, findet ihr hier eine Möglichkeit die Ergebnisse zu eingegebenen Instanzen zu ermitteln. Unter Umständen findet ihr dort sogar Probleminstanzen vor, die Benutzer vor euch getestet haben.

Hinweise zu den Vorträgen

  • Wichtig: Spätestens ein bis zwei Wochen vor eurem Vortrag solltet ihr einen Termin mit eurem Betreuer ausmachen, um euren kompletten Foliensatz durchzusprechen. Das sich daraus Änderungen an den Folien ergeben, ist die Regel (nicht die Ausnahme). Stellt also bitte sicher, dass ihr euch ein ausreichend grosses Zeitfenster für nötige Änderungen einräumt.

  • Die Länge der eigentlichen Vorträge soll jeweils zwischen 25 und 30 Minuten betragen. An die Vorträge schließt sich eine kurze offene Diskussion an, die sich auf den Inhalt des Vortrages aber auch auf den Vortrag an sich (Folien, Sprache) beziehen kann.

  • Ihr findet weitere wertvolle Hinweise zum Aufbau eines Vortrages, zum Layout von Folien und dem Halten des Vortrages selbst, auf den folgenden Seiten:

  1. Simon Peyton-Jones (Microsoft Research, Cambridge): How to give a great research talk
  2. Andreas Zeller (U Saarland): Der perfekte Seminarvortrag
  • Die Sprache der Folien soll Englisch sein. Ob ihr den Vortrag auf Deutsch oder ebenfalls auf Englisch haltet, ist dabei euch überlassen.

  • Der Inhalt des Vortrags sollte das durch den ACM Programming Contest gestellte Problem genau erläutern und vielleicht an 1–2 Beispielen demonstrieren. Dabei solltet ihr betonen, was das Problem interessant und/oder knifflig macht. Den Rest des Vortrages solltet ihr (1) auf die Diskussion möglicher Lösungsansätze (es kann ja durchaus mehrere denkbare Lösungen geben) und (2) die Darstellung der Realisierung der von euch gewählten und implementierten Lösung verwenden. Wichtig: Auf einer Folie eures Vortrages sollet ihr möglichst genau begründen, warum ihr gerade die von euch gewählte Programmiersprache einsetzt. Falls ihr nur eine Programmiersprache beherrscht, verwendet diese Folie stattdessen darauf, 2–3 Features einer (fiktiven) Programmiersprache zu identifizieren, die euch bei der Formulierung der Lösung besonders hilfreich gewesen wären.

  • Eure Programm zur Lösung des Problems wird typischerweise einen algorithmischen Kern — oft wenige Zeilen — beinhalten. Diesen Kern, evtl. gekürzt und vereinfacht falls angebracht, könnt und sollt ihr während des Vortrags zeigen und erklären. Wenn sich der Code selbst nicht eignet, ist ein Flussdiagramm oder ähnliches vielleicht eine bessere Alternative. Routinen oder Code-Teile, die Eingabe/Ausgabe implementieren sind oft sekundär und gehören nicht in Ihren Vortrag.

  • Die tatsächliche Demonstration eures lauffähigen Programmes gehört ebenfalls zu einem gelungenen Vortrag. Sie kann nicht zuletzt sehr motivierend für eure Zuhörer sein. Auch hier gilt aber: kleine Beispiele, die den common case zeigen und nicht die vielleicht eher esoterischen Randfälle des Problems und seiner Lösung zum Inhalt haben.

  • Generell gilt: vermittelt das Prinzip eurer Lösung — eine genaue Studie des Code ist nicht angebracht. Es ist auch denkbar, (Ausschnitte des) Code ausschliesslich ganz am Ende des Vortrages, auf sog. Backup-Folien in den Foliensatz aufzunehmen. Diese Folien zeigt man nur, wenn die Diskussion nach dem Vortrag oder spezifische Nachfragen dazu führen sollten. Wenn der Weg zur Lösung (nicht die Lösung selbst) systematisch war und einen eye opener enthält, dann kann das sehr zum Verständnisbildung beitragen. Die eher wahllose Darstellung von ''hab's mal probiert, ging dann aber doch schief''-Versuchen verwirrt jedoch eher.

  • Beachtet, dass beim ACM Programming Contest allgemein wohlgeformte Inputs vorausgesetzt werden dürfen. Eine explizite Behandlung illegaler Eingaben könnt ihr auch im Rahmen dieses Seminars ignorieren.

  • Zur Erstellung eurer Folien können wir euch die LaTeX-Class Beamer empfehlen.

Hinweise zu den Ausarbeitungen

  • Die Ausarbeitung eurer Vorträge erfolgt ausnahmslos in LaTeX. Hierfür soll die zweispaltige Formatvorlage SIGCONF Proceedings der ACM verwendet werden. Ihr könnt die Original-Vorlage herunterladen oder diese reduzierte Version benutzen. Die Ausarbeitung soll insgesamt 4 Seiten umfassen und auf Englisch verfasst werden.

  • Für Bilder empfehlen wir euch im Weiteren das LaTeX-Paket TikZ zu verwenden.


Additional material (code, data)