Programming语言讲解、辅导Java，C++程序设计、Java编程辅导
- 首页 >> Matlab编程 Algorithms Programming Project
1 Problem Definition
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.
2 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 Θ(m3n
3
) 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.]
3 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) space.
Task2 Give an iterative BottomUp implementation of Alg1 using O(n) space.
Task3 Give an implementation of Alg2 using O(1) space.
Task4 Give a iterative BottomUp implementation of Alg3 using O(n) space.
4 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.
1
For convenience assume that 1 ≤ m, n ≤ 2
31, 0 ≤ h ≤ 2
15, and ∀i, j 0 ≤ p[i, j] ≤ 2
15
.
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.
5 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.
6 Submission
The following contents are required for submission:
1. Makefile: Your makefile must be directly under the zip folder. No nested directories. Do
not locate the executable file in any directory too.
2. Source code: should include detailed comments next to each non-trivial block of code
lines.
3. Report: The report must be in PDF format. For each dynamic programming algorithm
design task, you need to (i) state a mathematical recursive formulation expressing the
optimal substructures. (ii) argue the optimal substructure (correctness). (iii) make a time
and space complexity analysis. For each programming tasks, comment on ease of implementation,
technicalities, performance. More importantly make sure to report on your
experimental study including at least two comparative plots.
4. Bundle: Compress all your files together using a zip utility and submit through the
Canvas system. Your submission should be named “LastNameFirstName.zip”.
7 Grading Policy
Grading will be based on the correctness and efficiency of algorithms and the quality of the
report:
• Program 60%. Correct/efficient design and implementation/execution.
• Report 40%. Write up on your design, analysis, programming experience, and experimental
study..
2
1 Problem Definition
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.
2 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 Θ(m3n
3
) 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.]
3 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) space.
Task2 Give an iterative BottomUp implementation of Alg1 using O(n) space.
Task3 Give an implementation of Alg2 using O(1) space.
Task4 Give a iterative BottomUp implementation of Alg3 using O(n) space.
4 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.
1
For convenience assume that 1 ≤ m, n ≤ 2
31, 0 ≤ h ≤ 2
15, and ∀i, j 0 ≤ p[i, j] ≤ 2
15
.
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.
5 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.
6 Submission
The following contents are required for submission:
1. Makefile: Your makefile must be directly under the zip folder. No nested directories. Do
not locate the executable file in any directory too.
2. Source code: should include detailed comments next to each non-trivial block of code
lines.
3. Report: The report must be in PDF format. For each dynamic programming algorithm
design task, you need to (i) state a mathematical recursive formulation expressing the
optimal substructures. (ii) argue the optimal substructure (correctness). (iii) make a time
and space complexity analysis. For each programming tasks, comment on ease of implementation,
technicalities, performance. More importantly make sure to report on your
experimental study including at least two comparative plots.
4. Bundle: Compress all your files together using a zip utility and submit through the
Canvas system. Your submission should be named “LastNameFirstName.zip”.
7 Grading Policy
Grading will be based on the correctness and efficiency of algorithms and the quality of the
report:
• Program 60%. Correct/efficient design and implementation/execution.
• Report 40%. Write up on your design, analysis, programming experience, and experimental
study..
2