首页 >
> 详细

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

联系我们

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

- Csse1001 Assignment 3 2021-01-10
- Comp3506/7505 Homework 4 – Graph Algo 2021-01-10
- Unix & C Programming (Comp1000) Assign... 2021-01-10
- Ece 209 Program 3: Market 2021-01-10
- Informatics 1 — Functional Programming 2021-01-10
- Cisc/Cmpe 452/Cogs400 Assignment 2 2021-01-10
- Fit2100 Operating Systems Assignment #... 2021-01-10
- Csci 1100 — Homework 5 2021-01-10
- Comp9444 Neural Networks And Deep Lea... 2021-01-10
- Assignment Case: German Credit 2021-01-10
- 48024 Applications Programming Assign... 2021-01-10
- Cs 405/805-001: Computer Graphics Ass... 2021-01-10
- Cse 434, Sln 70608 — Computer Networks 2021-01-10
- Corpfin 2503 - Business Data Analytics 2021-01-10
- Cis 455 / 555: Internet And Web System... 2021-01-10
- Cs110留学生编程代写、代做c++程序实验、Program程序语言调试帮做 2021-01-10
- Csc8021程序代做、代写networks编程语言、代做c/C++，Jav 2021-01-10
- 代写program编程语言、代做python，C++，Java程序设计帮做j 2021-01-10
- R编程课程代写、代做program程序语言、R程序实验代做代写databas 2021-01-09
- Data编程设计代做、代写java程序语言、Java程序实验调试代写r语言程 2021-01-09