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.
GraderWe 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.
- Python tutorial
- Hands-On steps to get started with PyCharm and python 3.6
- Python Cheat Sheet
- Official Python Doc
- Solving the first round in Python
- recommended grader tasks: addition, multi-adder, FizzBuzz
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.
- Graph Cheat Sheet
- Graph Lecture Blackboard
- recommended tasks on the grader: grepr, illuminati
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.
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?
- Greedy blackboard, whiteboard
- recommended tasks on the grader: binge, allotment
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