COP4533 Project 1: Greedy & DP for Art Exhibition Curation

Introduction to Algorithm Abstraction for Art Curation

In the COP4533 Project 1, you tackle a classic optimization problem: given a sequence of paintings with heights and widths, partition them into platforms of fixed width W to minimize the sum of the tallest painting on each platform. This problem, known as algorithm abstraction and design, challenges you to create efficient solutions for special cases (greedy) and the general case (dynamic programming). As of May 11, 2026, this project remains a cornerstone for learning algorithmic thinking—similar to how AI-powered gallery curators now use optimization to arrange digital exhibits in virtual museums.

Understanding the Problem

Imagine you are curating an exhibition of n paintings, each with a base width wi and height hi. They must stay in order. Platforms have maximum width W. The cost of a platform is the maximum height among paintings on it. Your goal: minimize total cost.

Example 1 (Non-increasing heights)

n = 7, W = 10, heights = [21,19,17,16,11,5,1], widths = [7,1,2,3,5,8,1]. Optimal: Platform1 = [s1…s3] cost 21, Platform2 = [s4…s5] cost 16, Platform3 = [s6…s7] cost 5 → total 42.

Example 2 (General)

n = 4, W = 10, heights = [8,10,9,7], widths = [8,1,2,2]. Optimal: Platform1 = [s1] cost 8, Platform2 = [s2…s4] cost 10 → total 18.

Example 3 (Unimodal)

n = 7, W = 10, heights = [12,10,9,7,8,10,11], widths = [3,2,3,4,3,2,3]. Optimal: Platform1 = [s1…s3] cost 12, Platform2 = [s4] cost 7, Platform3 = [s5…s7] cost 11 → total 30.

Milestone 1: Greedy Algorithms for Special Cases

Greedy algorithms make locally optimal choices. For ProblemS1 (non-increasing heights), a simple greedy works: start a new platform only when the next painting doesn't fit. For ProblemS2 (unimodal with a single minimum), a two-phase greedy can be designed.

Algorithm1 for ProblemS1 (Θ(n))

Algorithm1: Iterate paintings left to right. Maintain current platform width and current max height. If adding the next painting exceeds W, start a new platform. Add its cost. Otherwise, add the painting to the current platform and update max height. At the end, add the last platform's cost.

Correctness Proof: Since heights are non-increasing, the first painting on a platform is the tallest. Starting a new platform later only increases cost because the first painting on the next platform is even smaller. Hence, packing as many as possible into each platform minimizes the number of platforms and thus the sum of first heights.

Question1: Show that Algorithm1 fails for general ProblemG. Example: n=3, W=10, heights=[5,10,5], widths=[6,5,6]. Algorithm1: Platform1=[s1] cost5, Platform2=[s2] cost10, Platform3=[s3] cost5 → total20. Optimal: Platform1=[s1,s2] cost10, Platform2=[s3] cost5 → total15.

Question2: Show that Algorithm1 fails for ProblemS2 (unimodal). Example: n=3, W=10, heights=[10,5,10], widths=[6,5,6]. Algorithm1: Platform1=[s1] cost10, Platform2=[s2] cost5, Platform3=[s3] cost10 → total25. Optimal: Platform1=[s1,s2] cost10, Platform2=[s3] cost10 → total20.

Algorithm2 for ProblemS2 (Θ(n))

Algorithm2: Find the minimum height index k. Process left side (non-increasing) with a greedy that packs as many as possible. Process right side (non-decreasing) similarly but from right to left. Combine results.

Correctness Proof: On the left side, heights are non-increasing, so greedy works. On the right side, processing from right to left is equivalent to a non-increasing sequence when reversed. The optimal split at the minimum height ensures no interaction across sides.

Milestone 2: Dynamic Programming for General Problem

For the general case (ProblemG), we need DP because greedy fails. DP computes optimal cost for prefixes.

Algorithm3: Naive Θ(n2n-1)

Enumerate all possible ways to partition n paintings into platforms. This is exponential and only works for tiny n.

Algorithm4: DP O(n3) or O(n2W)

Define dp[i] = minimum cost for first i paintings. For each i, consider last platform starting at j (1 ≤ j ≤ i). Compute max height from j to i and total width. If width ≤ W, then dp[i] = min(dp[i], dp[j-1] + max_height). Complexity O(n3) if we recompute max each time, or O(n2) if we precompute.

Algorithm5: O(n2) DP

Improve by precomputing max heights for all intervals using a 2D array or by maintaining running max when iterating j backwards. For each i, iterate j from i down to 1, update current max height, and check width. This yields O(n2).

Implementation Tips

Use 0-indexed arrays. For greedy, simply loop. For DP, use a 1D array dp of size n+1, with dp[0] = 0. For memoization (top-down), write a recursive function with memo table. For bottom-up, fill dp iteratively. Test with random inputs of sizes 1000 to 5000.

Experimental Study

Generate random heights and widths (e.g., heights 1-100, widths 1-10). For each n = 1000,2000,3000,4000,5000, run your programs and record time. Plot time vs n. Expect greedy to be linear, DP quadratic. Compare Program1 vs Program2 vs Program5.

Conclusion

This project teaches you how to design algorithms for special cases (greedy) and general cases (DP). You'll appreciate why greedy fails when heights vary arbitrarily and how DP guarantees optimality at the cost of speed. This knowledge is directly applicable to modern problems like optimizing video streaming quality (selecting bitrate for segments) or arranging ads in a feed—both hot topics in AI and app development in 2026.