Algorithm Abstraction & Design: Greedy and DP for Art Exhibition Problem

Introduction to Algorithm Abstraction & Design

Algorithm abstraction is the art of stripping a problem down to its essential computational core. In this tutorial, we explore a classic assignment from COP4533: curating an art exhibition with paintings of varying heights and widths, placed on platforms of fixed width. The goal is to minimize total cost (sum of tallest painting per platform). This problem is a perfect vehicle for understanding greedy algorithms and dynamic programming.

Problem Definition

We have n paintings in a fixed order. Each painting i has width w_i and height h_i. Platforms have maximum width W. The cost of a platform is the maximum height among paintings on it. We must partition the sequence into contiguous platforms such that each platform's total width ≤ W, minimizing total cost.

Example: n=7, W=10, heights=[21,19,17,16,11,5,1], widths=[7,1,2,3,5,8,1]. Optimal: platform1: paintings 1-3 (cost 21), platform2: 4-5 (cost 16), platform3: 6-7 (cost 5), total=42.

Special Cases: Monotonic and Unimodal Heights

The assignment defines two special cases: ProblemS1 where heights are non-increasing (like Example 1), and ProblemS2 where heights are unimodal with a single minimum (like Example 3). For these, greedy algorithms run in Θ(n) time.

Greedy Algorithm for ProblemS1 (Non-increasing Heights)

Algorithm1: Process paintings left to right. Start a new platform with the first painting. While the next painting fits (total width ≤ W), add it to the current platform. If it doesn't fit, start a new platform. Since heights are non-increasing, the first painting on each platform is the tallest, so cost is simply the sum of heights of first paintings on each platform.

Correctness Proof: By induction. For any optimal solution, the first platform must contain a prefix of paintings; otherwise, we could shift paintings left without increasing cost. The greedy choice of taking as many as possible (up to W) is optimal because any shorter first platform would leave more width unused but not reduce cost (since heights are non-increasing, the first painting's height is fixed).

Counterexample for ProblemG (General): Consider heights=[10,1,10], widths=[5,5,5], W=10. Greedy (non-increasing assumption) would put painting1 alone (cost10), then painting2 and3 together? But painting2+3 width=10, cost=10, total=20. Optimal: painting1+2 (width10, cost10) and painting3 alone (cost10), total=20? Actually both 20? Let's adjust: heights=[10,9,10], widths=[5,5,5], W=10. Greedy: platform1: painting1 (cost10), platform2: painting2+3 (width10, cost10), total=20. Optimal: platform1: painting1+2 (width10, cost10), platform2: painting3 (cost10), total=20. They tie. Need a strict counterexample: heights=[10,8,10], widths=[6,4,6], W=10. Greedy: platform1: painting1 (cost10), platform2: painting2 (fits? width4, but painting3 doesn't? Actually painting2+3 width=10, so platform2: painting2+3 cost=10, total=20. Optimal: platform1: painting1+2 (width10, cost10), platform2: painting3 (cost10), total=20. Still tie. Let's use Example 2 from assignment: heights=[8,10,9,7], widths=[8,1,2,2], W=10. Greedy (non-increasing) would fail because heights are not non-increasing. But we need an example where heights are non-increasing? Actually ProblemG has arbitrary heights. So take heights=[5,4,3,2], widths=[5,5,5,5], W=10. Greedy: platform1: 1+2 (cost5), platform2: 3+4 (cost3), total=8. Optimal: platform1: 1+2+3? width15>10, no. So greedy is optimal here. A true counterexample: heights=[10,1,9], widths=[5,5,5], W=10. Greedy (non-increasing order not satisfied) would process left to right: platform1: painting1 (cost10), painting2 fits? width5+5=10, so add painting2, cost still 10, then painting3 doesn't fit (width15>10), so platform2: painting3 (cost9), total=19. Optimal: platform1: painting1+2 (cost10), platform2: painting3 (cost9) total=19. Still same. Need a case where greedy fails: heights=[9,8,7], widths=[4,4,4], W=8. Greedy: platform1: 1+2 (width8, cost9), platform2: 3 (cost7), total=16. Optimal: platform1: 1 (cost9), platform2: 2+3 (width8, cost8), total=17? Actually 9+8=17 >16. So greedy is better. Hmm. The classic counterexample is when a tall painting in the middle forces a split. Let's use: heights=[10,1,10], widths=[5,5,5], W=10. Greedy: platform1: painting1+2 (width10, cost10), platform2: painting3 (cost10), total=20. Optimal: platform1: painting1 (cost10), platform2: painting2+3 (width10, cost10), total=20. Tie. So greedy works for this? Actually the assignment says Algorithm1 does not always solve ProblemG. So we need a valid counterexample. Consider: heights=[5,4,3,2,1], widths=[5,5,5,5,5], W=10. Greedy: platform1: 1+2 (cost5), platform2: 3+4 (cost3), platform3: 5 (cost1), total=9. Optimal: platform1: 1+2+3? width15>10, no. So 9 is optimal. Another try: heights=[10,9,8,7], widths=[6,2,2,6], W=10. Greedy: platform1: 1+2 (width8, cost10), platform2: 3+4 (width8, cost8), total=18. Optimal: platform1: 1 (cost10), platform2: 2+3+4 (width10, cost9), total=19. So greedy gives 18 < 19, so greedy is better? Actually we want greedy to give higher cost. Let's swap: heights=[7,8,9,10], widths=[6,2,2,6], W=10. Greedy: platform1: 1 (cost7), platform2: 2+3+4 (width10, cost10), total=17. Optimal: platform1: 1+2+3 (width10, cost8), platform2: 4 (cost10), total=18. So greedy gives 17 < 18. Still better. The assignment's Example 2 shows a case where greedy would fail if applied naively. In Example 2, heights=[8,10,9,7], widths=[8,1,2,2], W=10. A greedy that always starts a new platform when a painting doesn't fit would produce: platform1: painting1 (cost8), painting2 fits? width8+1=9≤10, so add painting2 (cost becomes 10), painting3 fits? width9+2=11>10, so start new platform: platform2: painting3 (cost9), painting4 fits? width9+2=11>10, so start new platform: platform3: painting4 (cost7). Total=8+9+7=24. But optimal is 18 (platform1: painting1 alone cost8, platform2: paintings2-4 cost10). So greedy fails because it greedily adds painting2 to platform1, increasing cost from 8 to 10, when it would be better to leave painting2 for later. This is a valid counterexample for ProblemG.

Counterexample for ProblemS2: ProblemS2 has unimodal heights (first decreasing then increasing). Example: heights=[10,9,8,7,8,9,10], widths=[5,1,1,1,1,1,5], W=10. Greedy (non-increasing assumption) would process left to right: platform1: painting1 (cost10), painting2 fits? width5+1=6≤10, add (cost still 10), continue adding until painting7? width5+1+1+1+1+1+5=15>10, so platform1: paintings1-6 (width10, cost10), platform2: painting7 (cost10), total=20. Optimal: platform1: painting1 (cost10), platform2: paintings2-6 (width5, cost9? Actually max height among 9,8,7,8,9 is 9), platform3: painting7 (cost10), total=10+9+10=29? That's worse. Let's design a proper counterexample. We need heights that first decrease then increase. Example: heights=[12,10,9,7,8,10,11] from Example 3. Greedy (non-increasing) would: platform1: painting1 (cost12), painting2 fits? width3+2=5≤10, add (cost12), painting3 fits? width5+3=8≤10, add (cost12), painting4 fits? width8+4=12>10, stop. So platform1: paintings1-3 (cost12), platform2: painting4 (cost7), painting5 fits? width4+3=7≤10, add (cost8), painting6 fits? width7+2=9≤10, add (cost10), painting7 fits? width9+3=12>10, stop. So platform2: paintings4-6 (cost10), platform3: painting7 (cost11), total=12+10+11=33. Optimal from assignment: platform1: 1-3 (cost12), platform2: 4 alone (cost7), platform3: 5-7 (cost11), total=30. Greedy gives 33 > 30, so it fails.

Greedy Algorithm for ProblemS2 (Unimodal Heights)

Algorithm2: Since heights decrease then increase, the optimal strategy is to place the minimum-height painting in its own platform or with neighbors? Actually the assignment's Algorithm2 is not specified here, but we can design one: Find the minimum height painting (index k). Then greedily expand left and right? A known greedy for unimodal sequences: process from left to right but reset when height increases? The assignment expects a Θ(n) algorithm. One approach: treat the sequence as two monotonic parts: decreasing left part and increasing right part. For the left part (decreasing), use Algorithm1. For the right part (increasing), reverse the sequence and use Algorithm1 (since reversing makes it decreasing). Then combine? But careful: the minimum point might be shared. A simpler greedy: start from the minimum and expand outward, always adding the next painting if it fits, but that may not be optimal. The assignment's solution likely involves scanning left to right while maintaining a stack or something. However, for this tutorial, we focus on the general concepts.

Dynamic Programming for ProblemG

For the general case, dynamic programming is needed. Let dp[i] = minimum cost for first i paintings. Then dp[0]=0, and for i from 1 to n, dp[i] = min_{j < i, sum_{k=j+1}^i w_k ≤ W} ( dp[j] + max_{k=j+1}^i h_k ). This is O(n^2) if we compute max on the fly. The assignment asks for O(n^2) algorithm (Algorithm5). We can compute dp[i] by iterating j backwards, maintaining current max height and total width.

Algorithm5 (Bottom-Up DP): Initialize dp[0]=0. For i=1..n: set totalWidth=0, maxHeight=0; for j=i-1 down to 0: totalWidth += w_{j+1}; if totalWidth > W: break; maxHeight = max(maxHeight, h_{j+1}); dp[i] = min(dp[i], dp[j] + maxHeight). Return dp[n].

This runs in O(n^2) time and O(n) space.

Experimental Study & Performance Analysis

You will implement these algorithms and test on random inputs of sizes n=1000,2000,...,5000. Plot running time vs input size. Greedy algorithms should show linear time, while DP shows quadratic. Use Python's time module for measurements. Generate random heights and widths (e.g., heights between 1 and 100, widths between 1 and 10, W=20). Ensure inputs are valid (widths ≤ W individually).

Conclusion

This project teaches you to recognize when greedy works (monotonic or unimodal structures) and when DP is necessary. The art exhibition problem is a classic example of sequence partitioning with cost based on maximum. Understanding these patterns is crucial for algorithm design in coding interviews and real-world applications like resource allocation in cloud computing or advertising placement.