Algorithms-Programming Project Solved

Consider a city in Florida named Gridville that has a grid layout of m × n cells. Associated with each cell (i,j) where i = 1,...,m and j = 1,...,n, Gridville architectural board assigns a non-negative number p[i,j] indicating the largest possible number of floors allowed to build on that block. A developer company named AlgoTowers is interested to find the largest possible area (shaped square or rectangle) of blocks within city limits that allows a building of height at least h.

1         Algorithm Design Tasks
Alg1 Design a Θ(mn) time Dynamic Programming algorithm for computing a largest area square block with all cells have the height permit value at least h.

Alg2 Design a Θ(m3n3) time Brute Force algorithm for computing a largest area rectangle block with all cells have the height permit value at least h.

Alg3 Design a Θ(mn) time Dynamic Programming algorithm for computing a largest area rectangle block with all cells have the height permit value at least h.

[Hint: For gradual progress and also partial credit you might consider working on a O(mn2)-time algorithm design first.]

2         Programming Tasks
Once you have the dynamic programming formulations for the algorithm design tasks, you should have an implementation for each of the following programming procedures:

Task1 Give a recursive implementation of Alg1 using memoization and O(mn) extra space.

Task2 Give an iterative BottomUp implementation of Alg1 using O(n) extra space.

Task3 Give an implementation of Alg2 using O(1) extra space.

Task4 Give an iterative BottomUp implementation of Alg3 using O(mn) extra space.

3         Language/Input/Output Specifications
You may use Java or C++. Your program must compile/run on the Thunder CISE server using gcc/g++ or standard JDK. You may access the server using SSH client on thunder.cise.ufl.edu. You must write a makefile document that creates an executable named AlgoTowers. The task is passed by an argument, e.g., when AlgoTowers 3 is called from the terminal, your program needs to execute the implementation of Task3.

Input. Your program will read input from standard input (stdin) in the following order:

•    Line 1 consists three integers m, n, h separated by one space character.

•    For the next m lines, line i+1 consist of n integers p[i,1],p[i,2],...,p[i,n] in this particular order separated by one space character.

For convenience assume that 1 ≤ m,n ≤ 231, 0 ≤ h ≤ 215, and ∀i,j 0 ≤ p[i,j] ≤ 215.

Output. Print four integers x1,y1,x2,y2 to standard output (stdout) separated by a space character, where (x1,y1) is the upper left corner and (x2,y2) is the lower right corner of the optimal solution region.

4         Experimental Comparative Study
You are expected to test your implementations extensively for correctness and performance. For this purpose, you should create randomly generated input files of various sizes. Then, you should do a performance comparison between Task 1 and Task 2 and between Task 3 and Task 4. For each comparison, generate a two dimensional plot of running time (y-axis) against input size (x-axis). These should be included in your report along with additional comments/observations. Feel free to do additional comparative study, e.g., you may compare do a performance comparison between Task 1 and Task 3 by adjusting the Task3 solution for square shaped regions.