Mastering Algorithm Abstraction & Design: A Step-by-Step Guide to Greedy and Dynamic Programming for the Art Exhibition Problem

Introduction to Algorithm Abstraction & Design

In computer science, algorithm abstraction is the art of seeing beyond the surface of a problem to its core computational structure. The art exhibition problem from COP4533 Project 1 is a perfect example: you have n paintings with fixed sequence, each with width wi and height hi, and display platforms of maximum width W. The goal is to minimize total cost (sum of max heights per platform). This problem appears in many modern contexts: from AI-driven museum layout optimization to resource allocation in cloud computing. In this tutorial, we'll break down the greedy and dynamic programming approaches, using timely analogies from gaming and AI to make the concepts stick.

Problem Variants and Their Significance

The assignment defines three variants: ProblemG (general case), ProblemS1 (non-increasing heights), and ProblemS2 (unimodal heights with a single local minimum). Understanding these variants is crucial because real-world data often has patterns. For instance, in a gaming leaderboard, player scores might be sorted (non-increasing) or have a peak (unimodal). By mastering these special cases, you'll be better equipped to design efficient algorithms for the general case.

Greedy Algorithm for ProblemS1 (Non-Increasing Heights)

Algorithm Design

When heights are non-increasing (h1 ≥ h2 ≥ ... ≥ hn), a simple greedy strategy works: place paintings on the current platform until adding the next painting would exceed width W, then start a new platform. This runs in Θ(n) time because we scan the sequence once.

Correctness Proof

We prove by exchange argument. Suppose an optimal solution differs from the greedy one. Let the first platform where they differ be platform k. The greedy platform contains paintings from some start index i to j, while the optimal might end earlier. Because heights are non-increasing, the cost contributed by the greedy platform is at most the cost of the optimal platform (since the first painting is the tallest in both). By swapping, we can transform the optimal solution into the greedy one without increasing cost. Thus, greedy is optimal.

Counterexample for ProblemG

Consider n=3, W=10, heights=[10,5,8], widths=[6,5,5]. Greedy (non-increasing assumption fails) would place painting1 alone (cost 10), then painting2+3 (max height 8, total cost 18). But optimal is painting1+2 (max 10) and painting3 alone (8), total cost 18? Actually both 18? Wait, let's compute: greedy: platform1: [1] cost10, platform2: [2,3] max(5,8)=8 total18. Optimal: platform1: [1,2] max10 cost10, platform2: [3] cost8 total18 same. Need a better counterexample: n=4, W=10, heights=[9,7,8,6], widths=[4,4,4,4]. Greedy: platform1: [1,2] max9 cost9, platform2: [3,4] max8 cost8 total17. Optimal: platform1: [1] cost9, platform2: [2,3] max8 cost8, platform3: [4] cost6 total23 worse. Actually greedy wins. Let's find one where greedy fails: n=3, W=10, heights=[10,1,9], widths=[5,5,5]. Greedy: platform1: [1,2] max10 cost10, platform2: [3] cost9 total19. Optimal: platform1: [1] cost10, platform2: [2,3] max9 cost9 total19 same. Hmm. Classic counterexample: n=4, W=6, heights=[5,4,3,2], widths=[3,3,3,3]. Greedy: platform1: [1,2] max5 cost5, platform2: [3,4] max3 cost3 total8. Optimal: platform1: [1] cost5, platform2: [2,3] max4 cost4, platform3: [4] cost2 total11 worse. So greedy works for non-increasing? Actually the problem states that greedy for ProblemS1 might not work for ProblemG. Let's design: n=3, W=5, heights=[5,4,3], widths=[2,3,2]. Greedy: platform1: [1] cost5, platform2: [2] cost4, platform3: [3] cost3 total12. Optimal: platform1: [1,2] max5 cost5, platform2: [3] cost3 total8. So greedy fails because it doesn't consider that placing painting1 alone allows painting2+3 to fit? Wait greedy for non-increasing would place painting1 then painting2? Actually with non-increasing heights, greedy as defined (fill platform until width exceeded) would place painting1 and painting2 together? width1+width2=5, so platform1: [1,2] cost5, then painting3 alone cost3 total8 optimal. So greedy works. The counterexample must be when heights are not non-increasing. For ProblemG, heights can be any order. Example: n=3, W=10, heights=[5,10,5], widths=[6,5,6]. Greedy (using same fill strategy) would place painting1 alone (cost5), then painting2 alone (cost10), then painting3 alone (cost5) total20. Optimal: platform1: [1,3] max5 cost5? but widths 6+6=12>10, so not. Actually optimal: platform1: [1] cost5, platform2: [2,3] max10 cost10 total15? widths 5+6=11>10, so platform2: [2] cost10, platform3: [3] cost5 total20 same. Need better: n=4, W=10, heights=[3,10,4,7], widths=[4,3,4,3]. Greedy fill: platform1: [1] cost3, platform2: [2] cost10, platform3: [3,4] max7 cost7 total20. Optimal: platform1: [1,2] max10 cost10, platform2: [3,4] max7 cost7 total17. So greedy fails.

Counterexample for ProblemS2

ProblemS2 has unimodal heights (decreasing then increasing). Example: n=4, W=10, heights=[10,8,5,9], widths=[3,3,3,3]. Greedy for non-increasing (Algorithm1) would treat as non-increasing? But actually it's not monotonic. Greedy fill: platform1: [1,2] max10 cost10, platform2: [3,4] max9 cost9 total19. Optimal: platform1: [1] cost10, platform2: [2,3] max8 cost8, platform3: [4] cost9 total27 worse. So greedy works? Need a case where greedy fails: n=5, W=10, heights=[9,7,5,6,8], widths=[2,3,2,3,2]. Greedy fill: platform1: [1,2] max9 cost9, platform2: [3,4] max6 cost6, platform3: [5] cost8 total23. Optimal: platform1: [1,2,3] max9 cost9, platform2: [4,5] max8 cost8 total17. So greedy fails because it doesn't see that combining later paintings reduces cost.

Greedy Algorithm for ProblemS2 (Unimodal Heights)

Algorithm Design

For unimodal heights (decreasing then increasing), we can use a two-pointer greedy: start from both ends and fill platforms from left and right. The idea is to pair paintings from the decreasing part with those from the increasing part to balance heights. Specifically, we can process from left until we hit the minimum, then from right, always adding to the platform with smaller current max height to minimize cost. This runs in Θ(n).

Correctness Proof

The proof uses the fact that the optimal solution can be transformed into a symmetric one where platforms are formed by contiguous segments from left and right. The greedy algorithm builds these segments optimally by always choosing the side with the smaller current max height, ensuring that the cost is minimized.

Dynamic Programming for ProblemG

Naive Algorithm (Θ(n2^(n-1)))

Enumerate all possible ways to split the sequence into platforms. There are 2^(n-1) possible partitions (each gap between paintings can be a break or not). For each partition, compute cost in O(n) time. This is only feasible for very small n (e.g., n ≤ 20).

Dynamic Programming O(n^3)

Define dp[i] = minimum cost for first i paintings. Then dp[0]=0, and for each i from 1 to n, dp[i] = min_{j < i and sum of widths from j+1 to i ≤ W} (dp[j] + max height from j+1 to i). This is O(n^3) if we compute max height naively for each j, but we can precompute max heights in O(n^2) to get O(n^2) per i? Actually precomputing max for all intervals is O(n^2), then dp computation is O(n^2) total. So O(n^2) if we precompute. But the assignment asks for O(n^3) or O(n^2|W|). The O(n^2|W|) variant uses a different state: dp[i][w] but that's not typical.

Optimal Dynamic Programming O(n^2)

We can improve by noting that the max height for a platform is the maximum of the first painting's height and the max of the rest. Using monotonic queue or precomputation, we can achieve O(n^2). Actually the standard DP is O(n^2) if we precompute the cost of each possible platform (j..i) in O(n^2) and then DP is O(n^2). So overall O(n^2).

Implementation Tips and Performance Analysis

When implementing, use 1-indexed arrays for convenience. For the greedy algorithms, simple loops suffice. For DP, use a 2D array for max heights and a 1D array for dp. Test with random inputs of sizes up to 5000 to see O(n^2) vs O(n^3) differences. Plot running times to verify theoretical complexities.

Connecting to Real-World Trends

This problem is analogous to resource allocation in AI training pipelines: you have tasks (paintings) with resource requirements (widths) and time (heights), and you want to minimize total time across machines (platforms). In gaming, think of level design where each level has a difficulty (height) and length (width), and you want to group levels into sessions to minimize maximum difficulty per session. In finance, portfolio optimization where assets are ordered and you want to minimize risk (max volatility) per bucket.

Conclusion

Algorithm abstraction and design is a critical skill for solving complex problems. By mastering greedy and DP approaches for the art exhibition problem, you've learned how to identify patterns, prove correctness, and optimize performance. These techniques are directly applicable to modern challenges in AI, gaming, and finance. Keep practicing with different problem variants to sharpen your skills.