/Tree-Plantation-Problem

This repository contains a collection of different dynamic programing algorithms designed to solve the tree plantation problem.

Primary LanguagePython

Tree-Plantation-Problem

Problem Definition

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 Requirement

Given 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.

Steps to run

To execute algorithm use python3 main.py ALG#, where # is algorithm no.

For example, to execute alg3

$ python3 main.py alg3

Algorithms Included

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)

Experimental Comparative Study

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.

Problem1:

Problem2:

Problem3:

Implementation Details

For detailed implementation information, please refer to the project report.