Intermediate algorithms (optional)
The distribution network: recursion, DP, graphs, Dijkstra, amortized complexity
In this chapter, you will learn to
- Think recursively and avoid recomputing (dynamic programming)
- Model a problem as a graph and search it for paths
- Estimate the real cost of a data structure
Tools: Python
8 exercises
Each exercise is graded automatically, in your browser. The full statements are available once you have an account.
What this is for in real life
Many real problems are networks or chains of choices, and trying every possibility is out of the question. - GPS. Finding the fastest route through millions of junctions is a shortest-path problem on a graph.…
Russian dolls
Welcome to the LogiMax distribution network! You are the new engineer in charge of optimizing operations. First problem: the central warehouse's inventory. Goods are stored in nested boxes: a box can contain…
The cheapest path
LogiMax products travel through a relay network organized as a grid. Each relay has a transit cost (in euros). A product starts from the top-left corner and must reach the bottom-right corner. At each…
The parcel tower
The LogiMax warehouse stacks parcels on pallets. For stability, each parcel must be strictly smaller (in width AND in height) than the one beneath it. You are given a list of parcels, each described by…
Urgent deliveries
The LogiMax sorting station never releases orders in their arrival order: at any moment, it is the most urgent one that goes out first, and new orders keep dropping in while the previous ones are being shipped. Each…
The road network
The LogiMax network consists of warehouses connected by one-way roads. You are given the map as an adjacency list: a dictionary where each key is a warehouse and the value is the list of warehouses directly…
The shortest route
Now the LogiMax roads have distances! The network is given as a weighted adjacency dictionary:
The expandable warehouse
The LogiMax warehouse uses a dynamic shelving system. At the start, there is room for 1 parcel. When the shelf is full and a new parcel arrives, a shelf twice as large is built and all the existing parcels are…