联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp

您当前位置:首页 >> Java编程Java编程

日期:2020-11-18 11:36

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


版权所有:留学生编程辅导网 2020 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp