Algorithms and Datastructures Project
For this assignment we received a 9.6 and got put in the top 10 best solutions of the class.
The problem in short
The problem concerns the flooding of the Dutch polders. There is a provided graph where some notes are marked as containing a pumping station and each edge has a different provided cost to traverse. When you are at a node with a pump you may turn it on to start pumping out water at a constant flow. The problem in short is: given a certain graph and starting location how can you traverse this graph such that you pump as much water out of the polders in given a certain time frame.
Key parts of our solution
We first reduced the graph to only contain nodes marked as having a pump. This was done using Dijkstra’s algorithm.
For the second part we utilised dynamic programming. We reduced the problem to minimizing the sum of the commencement times of the pumps. We have developed a rather extensive recurrence relation for this part of the solution, which is further specified and mathematically supported (not a formal proof) in our report included in the git repository.
Key skills learned/used in this project
- Working on graph theoretic problems and implementing algorithms such as Dijkstra’s algorithm
- Being able come up with and implement more advanced types of algorithms such as a Dynamic programming solution
- Being able to mathematically support/proof validity of a solution to a certain algorithm
- Being able to determine complexity of simple algorithms, like Dijkstra’s algorithm, and more complicated algorithms, which make use of recurrence relations
- Effectively using hashmaps/hashtables (sets and dictionaries) in Python to speed-up an implemention