# Workshop Ressources

## Overview

This is a collection of all the material that was covered in our workshops in Lausanne, Bern and Zurich. The resources are ordered by the topics of the respective days: Python, Graphs, DP. Additionaly you can find some sample solutions to tasks that are on the grader.

We did not limit ourself to programming the whole workshop. Check out how our participants did perform in the scavenger hunt through Zurich. Many impressions can be found on Flickr, Instagram or Facebook and on our blog.

## Day 1 - Python

On the first day we had a closer look at the programming language python. The first lecture “Python Hands-On” was about learning the essential basics for further lessons. This included reading, outputting data from/to a file and solving the first sushi subtask.

The second lecture “Intro to Algorithmics” explained how to measure the efficiency of an algorithm and how to determine if an idea is fast enough for large problem sets. The lecture is based on the script available in our Wiki.

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

The last two lectures were about common data structures in python which you should know to solve our tasks. First we had a closer look at the fundamental structures: list, stack and queue. The more advanced ones we covered in the second lecture were heap, set and map.

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

## Day 2 - Graphs

Day two was all about one of the most common and important type of tasks: graphs. The first lecture was an introduction on what exactly a graph is and what properties they have. The second part was about graph representation in python.

Now that graphs are introduced, we had a closer look at two most famous graph traversal algorithms: BFS and DFS. With these two algorithms, one can explore the graph in a very efficient way and they are a must have for every programmers tool kit. BFS can be used to determine the shortest path between two vertices and DFS can be used to check if a graph can be two-colored.

• 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

## Day 3 - DP

On the last day the topic was Dynamic Programming (DP). This is not just a specific algorithm for solving one single problem, it is a way of solving a whole class of problems. The most important rule of DP is: Don’t calculate anything twice! Whenever we encounter a similar subproblem, that we already solved, we can make use of our previous work. Often, the implementation of such a dynamic problem is easy. To first figure out how to solve a given problem with DP and come up with the correct formula is the tricky part. Practicing on our tasks is the best way to get a feeling for it!

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

It is quite amazing what you can do with dynamic programming - ever wanted to figure out if you have the right coins to pay for your lunch without any change? You can exactly do this with the topic of the second lecture on DP: The subsetsum problem. Here we try to figure out if we can choose elements from a given set to reach an exact amount. Just like choosing coins from your wallet to pay the price of the lunch menu.

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

It seems as if the sky is the limit for DP. In our most advanced lecture we saw that the concept of DP can even be applied on graphs, which we covered on the second day. There exists a fascinating algorithm to determine the shortest path between all pairs of vertices in a given graph.

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

Last but not least, there was a lecture about greedy algorithms. Imagine after solving all these tasks you are tired and just want to sit back and watch as many different TV shows as possible. But how could you do that? What strategy might work - how can you be sure that your approach is correct?

## Solutions

This is a collection of solutions to some of our tasks on the grader. Try to solve them first yourself, if you have questions you can also always send us an email to info@soi.ch

## Stay hungry, stay foolish

Still hungry for more? Here are some ideas how to challenge yourself:

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