====== Beating the Worst Case ======

**Dozenten:** [[people:vonderheydt|Jean-Pierre]], [[people:marcuswilhelm|Marcus]]\\
**Campus-System:** [[https://campus.studium.kit.edu/search.php#!campus/all/event.asp?gguid=0x1AB3A415CF7140BA8611C6B13AD005F4| Veranstaltungsnr. 2400121]]\\
**Plätze: 16**\\
**Anmeldung:** Anmeldung mit Name und Matrikelnummer per Mail an [[people:vonderheydt|Jean-Pierre]] [[mailto:heydt@kit.edu|heydt@kit.edu]], alternativ einfach zum ersten Treffen kommen (first come first serve)\\
**GitLab:** [[https://gitlab.kit.edu/kit/iti/scale/templates/praktikum_beating_the_worst_case_framework|Repo des Frameworks auf GitLab]]
\\
\\

Bei dem Praktikum //Beating the Worst Case in Practice: Unerwartet effiziente Algorithmen// beschäftigen wir uns mit Algorithmen, die auf praktischen Instanzen deutlich effizienter sind, als theoretische Worst-Case Analysen erwarten lassen. Diese unerwartete Effizienz wird im Rahmen des Praktikums mit empirischen Methoden untersucht. Hierfür geben wir verschiedene algorithmische Ansätze und Probleme vor, die von den Studierenden selbstständig implementiert und evaluiert werden.
\\

===Lernziele:===
Die Studierenden
  * können das in den Grundlagenmodulen zur Algorithmentechnik erlernte Wissen praktisch anwenden, 
  * sind in der Lage eigenständig effiziente Implementierungen algorithmischer Verfahren anzufertigen,
  * beherrschen die Methodik zur praktischen Evaluierung von Algorithmen, inklusive der Aufarbeitung,
  * Analyse und Interpretation von Messdaten,
  * besitzen die Fähigkeit gefundene Ergebnisse zu kommunizieren. 

Die Teilnehmer sind außerdem in der Lage zu analysieren, welchen Einfluss typische Eigenschaften von Instanzen auf die Effizienz von Algorithmen haben.

=== Ablauf: ===
Es gibt zwei Phasen. In der ersten Phase werden die Teilnehmer anhand von Übungsblättern schrittweise an die empirische Analyse einer algorithmischen Fragestellung herangeführt. Anschließend wird in der zweiten Phase das bereits Gelernte angewandt, um einen weiteren Algorithmus empirisch zu untersuchen. Die Arbeit erfolgt hierbei in kleinen Teams.
\\
\\
Wir treffen uns zum ersten Termin am **25. Oktober um 15:45 in Raum 301** im Informatikgebäude. Im ersten Treffen werden alle Details bezüglich des weiteren Ablaufs besprochen.
\\
\\
**Folien** werden auf dieser Webseite hochgeladen.

=== Material ===

Aufgabe 0: Aufwärmübung
  * Aufgabenstellung: {{ :teaching:2023ws:beating_wc:blatt00.pdf |}}
  * Rätselinstanzen: {{ :teaching:2023ws:beating_wc:networks.zip |}}

Aufgabe 1:
  * Aufgabenstellung: {{ :teaching:2023ws:beating_wc:blatt01.pdf |}}

Aufgabe 2:
  * Aufgabenstellung: {{ :teaching:2023ws:beating_wc:blatt02.pdf |}}

Aufgabe 3:
  * Aufgabenstellung: {{ :teaching:2023ws:beating_wc:blatt03.pdf |}}

Aufgabe 4 / Ausarbeitung:
  * Aufgabenstellung / Hinweise: {{ :teaching:2023ws:beating_wc:blatt04.pdf |}}
    * Vorlage Ausarbeitung: LIPIcs ([[https://submission.dagstuhl.de/styles/download-tag/lipics/v2021.1.3/authors/zip/lipics-authors-v2021.1.3.zip|Template]], [[https://submission.dagstuhl.de/styles/instructions/86|Author Instructions]])

=== Slides ===

  * Intro-Slides: {{ :teaching:2023ws:beating_wc:lecture01.pdf|}}
  * Treffen 2: {{ :teaching:2023ws:beating_wc:lecture02.pdf |}} {{ :teaching:2023ws:beating_wc:lecture02_print.pdf |Druckversion}}
  * Treffen 3: {{ :teaching:2023ws:beating_wc:lecture03.pdf |}} {{ :teaching:2023ws:beating_wc:lecture03_print.pdf |Druckversion}}
  * Treffen 4: {{ :teaching:2023ws:beating_wc:lecture04.pdf |}} {{ :teaching:2023ws:beating_wc:lecture04_print.pdf |Druckversion}}
  * Treffen 5: {{ :teaching:2023ws:beating_wc:lecture05.pdf |}} {{ :teaching:2023ws:beating_wc:lecture05-print.pdf |Druckversion}}
  * Treffen 6: {{ :teaching:2023ws:beating_wc:lecture06.pdf |}} {{ :teaching:2023ws:beating_wc:lecture06-print.pdf |Druckversion}}
  * Treffen 7: {{ :teaching:2023ws:beating_wc:lecture07.pdf |}} {{ :teaching:2023ws:beating_wc:lecture07-print.pdf |Druckversion}}
  * Treffen 8: {{ :teaching:2023ws:beating_wc:lecture08.pdf |}} {{ :teaching:2023ws:beating_wc:lecture08-print.pdf |Druckversion}}