The project focuses on developing an algorithm to optimize tree planting in the town of Greenvale, where each plot of land has a minimum tree requirement assigned by the Parks and Recreation Department. The goal is to find the largest possible square-shaped area of plots within the town that meets specific tree planting criteria.
Problem 1: Maximum Square Area for Minimum Tree RequirementGiven a matrix p of dimensions m × n, representing the minimum number of trees required on each plot, and an integer h (positive), the algorithm aims to find the bounding indices of a square area where each plot enclosed requires a minimum of h trees to be planted.
Problem 2: Maximum Square Area with Corner Plot Flexibility
Similar to Problem 1, but with the additional flexibility that corner plots can have any number of trees required. The goal is to find the bounding indices of a square area where all but the corner plots enclosed require a minimum of h trees to be planted.
Problem 3: Limited Exception for Minimum Tree Requirement
Given the matrix p, an integer h (positive), and an additional parameter k (positive) representing the maximum number of plots that can have a minimum tree requirement of less than h, the algorithm aims to find the bounding indices of a square area meeting these criteria.
To execute algorithm use python3 main.py ALG#, where # is algorithm no.
For example, to execute alg3
$ python3 main.py alg3
For Problem 1
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| alg1 (Brute Force) | O(m3n3) | O(1) |
| alg2 | O(m2n2) | O(1) |
| alg3 (Dynamic Programming) | O(mn) | O(mn) |
For Problem 2
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| alg4 (Dynamic Programming) | O(mn2 | O(mn2) |
| alg5a (Top Down Recursion + Memoization) | O(mn) | O(mn) |
| alg5b (Bottom Up DP) | O(mn) | O(mn) |
For Problem 3
| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| alg6 (Brute Force) | O(m3n3) | O(1) |
| alg7a (Top Down Recursion + Memoization) | O(mnk) | O(1) |
| alg7b (Bottom Up DP) | O(mnk) | O(1) |
Following figures depict visual representations illustrating the execution time needed for various tasks across different input sizes, with m=n, h, and randomly generated matrix values.
For detailed implementation information, please refer to the project report.