1 Box-Stacking Given a set of 3D boxes, how can we stack them in the highest way given the following rules? • A box, A, can only be stacked on another box, B, if the base of A is smaller than the base of B (both depth and width) • There are 3 different ways to rotate each box: (h; min(d; w); max(d; w)) (d; min(h; w); max(h; w)) (w; min(d; h); max(d; h)) and we have an infinite supply of each rotation of each box. 2 Bellman-Ford The Bellman-Ford algorithm can be used to find the shortest path tree from a single vertex. It is similar to Dijkstra’s algorithm, in that regard, but it works on graphs with negative edges. Negative cycles, if found, cause the program to terminate since they create infinite loops. • Trace how Dijkstra’s algorithm runs on the graph below to see how it fails. • Bonus: Trace how Bellman-Ford runs and try to find ways to improve it. 1A B C Dk D1 2 1 −3 1 1 Figure 1: Graph with k-claw from a to Di; 1 ≤ i ≤ k. Shortest path tree from source A is highlighted red 2
