Workshop-Ressourcen

Übersicht

Dies ist eine Sammlung des gesamten Materials, das in unseren Workshops in Lausanne, Bern und Zürich behandelt wurde. Die Ressourcen sind nach den Themen der jeweiligen Tage geordnet: Python, Graphen und DP. Zusätzlich findest du hier einige Beispiellösungen für Aufgaben, die sich auf dem Grader befinden.

Grader

Wir haben nicht nur den ganzen Workshop programmiert. Sieh wie unsere Teilnehmer sich bei der Schnitzeljagd quer durch Zürich geschlagen haben.Viele Photos und Eindrücke sind auf Flickr, Instagram oder Facebook und auf unserem Blog.

Tag 1 - Python

Am ersten Tag haben wir uns die Programmiersprache Python genauer angesehen. Der erste Vortrag “Python Hands-On” befasste sich mit dem Erlernen der Grundlagen für den weiteren Unterricht. Dazu gehörte das Lesen sowie das Ausgeben von Daten aus/in eine Datei und das Lösen der ersten Sushi-Aufgabe.

Der zweite Vortrag “Intro to Algorithmics” erklärte, wie man die Effizienz eines Algorithmus messen und herausfinden kann, ob eine Idee schnell genug für große Problemsets ist. Die Vorlesung basiert auf dem in unserem Wiki verfügbaren Skript.

  • Introduction to Algorithmics: wiki script
  • recommended grader tasks: maxsubarray

Die letzten beiden Vorträge befassten sich mit den gängigen Datenstrukturen in Python, die man kennen sollte, um unsere Aufgaben zu lösen. Zuerst haben wir uns die grundlegenden Strukturen der List, des Stacks und der Queue genauer angesehen. Die Fortgeschritteneren, die wir in der zweiten Vorlesung behandelt haben, waren Heap, Set und Map.

  • recommended grader tasks for lists: cablecar, scoreboard, speedstats
  • recommended grader tasks for adv. datastructures: shop, supershop, 3sum

Tag 2 - Graphen

Am zweiten Tag ging es um eine der häufigsten und wichtigsten Art von Aufgaben: Graphen. Der erste Vortrag war eine Einführung über was genau ein Graph ist und welche Eigenschaften er hat. Der zweite Teil befasste sich mit der Implementierung in Python.

Nun, da die Graphen eingeführt sind, haben wir uns zwei der bekanntesten Graph Traversal Algorithmen näher angesehen: BFS und DFS. Mit diesen beiden Algorithmen kann man den Graphen sehr effizient erkunden und sie sind ein Muss für jeden Programmierer Toolkit. Mit BFS kann der kürzeste Weg zwischen zwei Knoten ermittelt werden und mit DFS kann geprüft werden, ob ein Graph zweigefärbt werden kann.

  • BFS: slides, wiki
  • DFS: handout, slides, wiki
  • recommended tasks for BFS on the grader: shortestpath, toilet
  • recommended tasks for DFS on the grader: components, passports

Tag 3 - DP

Am letzten Tag war das Thema Dynamic Programming (DP). Dies ist nicht nur ein spezifischer Algorithmus zur Lösung eines einzelnen Problems, sondern ein Weg, um eine ganze Klasse von Problemen zu lösen. Die wichtigste Regel von DP ist: Berechne nichts doppelt! Wann immer wir auf ein ähnliches Teilproblem stoßen, das wir bereits gelöst haben, können wir auf unsere bisherige Arbeit zurückgreifen. Oftmals ist die Implementierung eines solchen dynamischen Problems einfach. Zunächst herauszufinden, wie man ein bestimmtes Problem mit DP lösen kann und die richtige Formel zu bestimmen ist der schwierige Teil. Üben ist der beste Weg, um ein Gefühl dafür zu bekommen!

  • Dynamic Programming: wiki script
  • recommended tasks on the grader: fibonacci, trisum, trisumpath

Es ist ziemlich erstaunlich, was wir mit dynamischer Programmierung alles tun können - wolltest du schon immer herausfinden, ob du die richtige Münzen hast, um das Mittagessen exakt zu zahlen? Genau das kannst du mit dem Thema der zweiten Vorlesung zum Thema DP: Das Subsetsum-Problem. Hier versuchen wir herauszufinden, ob wir Elemente aus einer vorgegebenen Menge auswählen können, um einen genauen Betrag zu erreichen. Genauso wie Münzen aus dem Portemonnaie zu wählen, um den Preis für die Mahlzeit zu bezahlen.

  • DP Subsetsum: slides
  • recommended tasks on the grader: mensacheck, mensaexplicit

Es scheint, als ob DP keine Grenzen gesetzt sind. In unserem fortgeschrittenen Vortrag haben wir gesehen, dass sich das Konzept der DP auch auf Graphen anwenden lässt, die wir am zweiten Tag behandelt haben. Es existiert ein faszinierender Algorithmus, um den kürzesten Weg zwischen allen Knotenpaaren eines Graphen zu bestimmen.

  • DP All pair shortest path: slides
  • recommended tasks on the grader: sightseeingtour, centralbistro

Zu guter Letzt gab es einen Vortrag über gierige Algorithmen. Stelle dir vor, nach dem vielen lösen all dieser Aufgaben bist du müde und willst dich einfach nur zurücklehnen und so viele verschiedene TV-Shows wie möglich schauen. Aber wie könntest du das tun? Welche Strategie könnte funktionieren - wie kannst du dir sicher sein, dass dein Ansatz richtig ist?

Lösungen

Dies ist eine Sammlung von Lösungen für einige unserer Aufgaben auf dem Grader. Versuche sie erst selbst zu lösen, falls du Fragen hast kannst du uns jederzeit eine Email an info@soi.ch senden.

Stay hungry, stay foolish

Noch immer hungrig nach mehr? Hier sind einige Ideen, wie du dich selbst herausfordern kannst:

  • Tons of tasks on our grader
  • The first round is still running
  • Want to get to know some more algorithms? check out the wiki