Bachelorseminar Matching, Cake cutting and Apportionment

• Prüfungen
  • Seminarnote

Beschreibung

Inhalt

The main topic of this seminar are algorithms for matching problems and for fair allocation of divisible and indivisible goods under preferences.

Examples of matching problems are finding maximum matchings in bipartite graphs, stable marriage problems, and stable roommates problems.

Examples of allocation of indivisible goods are allocation of seminar places, the hospitals-residents problem, house allocation with existing tenants, and kidney exchange.

Algorithms for fair allocation of divisible goods range under the name of cake cutting protocols, where a cake is a metaphor for a divisible entity, and have various applications ranging from land estate, inheritance, broadcast time, advertisement space, and cloud computing.

Seminar-Leitung

Prof. Dr. Mila Majster-Cederbaum

Technische Fragen: Dr. Philipp Wendler

Termine

Das Seminar wird online und hauptsächlich asynchron stattfinden ohne regelmäßige Termine. Die verpflichtende Einführungsveranstaltung (am 14.04.2021 um 14:00 Uhr) und die Einzelgespräche finden live statt, die Termine werden noch bekanntgegeben. Die Vorträge werden als Videos hochgeladen.

Ablauf (aktualisiert)

Alle Studierenden erhalten ein konkretes Thema. Sie werden in Ihrem Thema und Ihrer Ausarbeitung individuell betreut.

Der Ablauf ist wie folgt:

1. Am Anfang des Semesters gibt es eine Einführungsveranstaltung, in der die Themen kurz vorgestellt werden. Die Anwesenheit ist verpflichtend. Anschließend können Sie Themenwünsche äußern, die im Abgleich mit den anderen Studierenden berücksichtigt werden.
2. Sie arbeiten sich in Ihr Thema ein in dem Sie sich mit der Literatur befassen und auch eine Internet-/Literaturrecherche dazu durchführen.
3. Sie erstellen die Ausarbeitung (ca. 10 Seiten), die ich durchsehe, kommentiere und in Einzelgesprächen individuell bespreche.
4. Basierend auf der Ausarbeitung erstellen Sie Folien für einen Vortrag von ca. 30 Minuten.
5. Zu den Vorträgen sollen Sie auf einer separaten Folie eine Beispielaufgabe für die Kommilitonen vorbereiten, die diese selbständig bearbeiten und dessen Ergebnis diese mir zusenden. Im Fall von Algorithmen kann dies ein Beispiel sein, auf das der Algorithmus angewandt werden soll.
6. Sie halten Ihren Vortrag für sich und zeichnen ihn auf (bitte mit Video, falls es nicht anders geht mindestens Folien plus Audio).
7. Bis 20.6.: Sie geben das Vortragsvideo ab.
8. Wir verteilen die Vortragsvideos und Folien an alle Teilnehmerinnen und Teilnehmer.
9. Bis 04.07. 08.07.: Sie wählen aus den Aufgaben Ihrer Kommilitoninnen und Kommilitonen 6 3 Aufgaben aus, bearbeiten diese, und geben das Ergebnis ab.

Alle Dokumente (Gliederung, Folien, Ausarbeitung, Aufgaben) senden Sie bitte immer als PDF per Mail an Frau Prof. Majster-Cederbaum. Für die Aufzeichnung und Abgabe der Vortragsvideos erhalten Sie noch technische Hinweise.

Sprache

Vortrag und Ausarbeitung können auf deutsch oder englisch sein.

Bewertungskriterien

Vortrag

• Inhalt: Motivation und Einführung, Gliederung, Argumentationskette, Abstraktionsniveau, Vollständigkeit
• Form: Form der Folien (Schriftgröße, Diagramme, Folien nicht überladen), freie Rede, sprachliche Verständlichkeit (deutliche Sprechweise, Wortwahl), Einhalten der Zeit

Der Vortrag soll ca. 30 Minuten dauern.

Ausarbeitung

• Darstellung: Klarheit des Textes, sprachliche Gewandtheit, äußere Form, Rechtschreibung, Quellenangaben, sinnvolle Darstellung von Abbildungen
• Hinführung: Abstract, Einleitung und Motivation
• Hauptteil: Argumentationskette, Darstellung der Hauptresultate
• Abschluss: Schlussbewertung und Zusammenfassung, Ausblick

Die Ausarbeitung soll ca. 10 Seiten lang sein.

Hörerkreis

Bachelor Informatik oder Medieninformatik

Institut

Institut für Informatik

Dozent:in

• Mila Majster-Cederbaum

Assistent:in

• Philipp Wendler

Kursteilnehmer:innen

14 von 14

Zentralanmeldung

Bachelorseminare

Anweisungen zur Bewerbung

Benötigte Vorkenntnisse: erfolgreiche Teilnahme an der Vorlesung “Algorithmen und Datenstrukturen”

Material

Das Kursmaterial ist nur für Mitglieder des Kurses einsehbar, also z.B. für Teilnehmer:innen, Tutor:innen, Korrektor:innen und Verwalter:innen.

Prüfungen

Name	Anmeldung ab	Anmeldung bis	Termin	Prüfungsanmeldung
Seminarnote				Nicht zur Prüfung angemeldet

Termine

Art	Zeit	Regulärer Raum	Notiz
Einführungsveranstaltung	Mi 14 Apr 2021 14:00–14:45	Raum wird nur Kurs-assoziierten Personen (Teilnehmer:innen, Tutor:innen, Korrektor:innen, etc.) angezeigt	Beginn s.t.