COMP 526代做、代写Bamboo Trimming、java语言代做、java编程调试

日期：2020-03-29 05:31

Programming Puzzle: Bamboo Trimming

back to main page — COMP 526 Applied Algorithmics

Programming Puzzle: Bamboo

Trimming

This continuous-assessment exercise consists of a small applied project

with algorithmic and programming components, including a real-time

leaderboard of the competition.

Will you be able to beat your classmates, or even your demonstrator?

You will be working on a real, challenging research problem, so the

intention is as much on the process of producing solutions to algorithmic

problems, as on the actual deliverable.

The Bamboo Trimming Problem

To offset the long hours of

sitting in classes, you are

a passionate gardener,

and your pride and joy is

your little forest of exotic

bamboos. However, being

one of the fastest-growing

plants on earth, the

bamboo plot requires

constant attention. In an

attempt to keep the effort manageable, you decide to each day cut down

exactly one of your the bamboo plants, and you cut it right back to the

roots.

Sebastian Research Teaching Blog About

2020/3/27 Programming Puzzle: Bamboo Trimming

Since your bamboos have vastly different growth rates, some of them need

more frequent cutting than others. You set out to find a periodic schedule

of which bamboo to cut each day, so as to minimize the maximal height of

your garden.

Formalization

You decide to mathematically model the task as follows. Given bamboos

with daily growth rates , we assume that after growing for days

(without cutting), bamboo will have height . Right after you cut a

bamboo, its height is 0, and so is the initial height of all bamboos at the

beginning.

Writing for the height of bamboo after days, and the bamboo

that you cut on day , we obtain:

The task is to find an infinite schedule of cuts that keeps the

maximal height as low as possible.

To simplify your planning, you decide to restrict your attention to periodic

schedules, i.e., a fixed, finite list of cuts that follow, and when you are

done, you simply start from the beginning again.

Inputs

Your garden contains five named bamboo plots with the growth rates of

the bamboos given below:

Unequal Pair: [1,199]

Fibonacci: [1,1,2,3,5,8,13,21]

Odds [3,3,3,5,5,7,7,9]

Powers3 [3,6,12,24,48,96,192,386]

Precision [2000,3999,4001]

n g1, … , gn ti t ⋅ gihi(t) i t c(t)th1(0) = h2(0) = ⋯ = hn(0) = 0;(t + 1) =

{h (t ≥ 0). igihi(t) + gi

if c(t) = i

otherwise

c : ℕ → [n] 0

sup (t) t∈ℕmaxi∈[n] hi

C

2020/3/27 Programming Puzzle: Bamboo Trimming

Design as good a periodic schedule as you can find for each of them!

Can you argue that your solutions are best possible?

Code template

We prepared a Java implementation of the bamboo-trimming problem that

you will use to evaluate your trimming schedules:

Java sources

There is one main class BambooX for each value of X in the list above. They

simulate the growth of the bamboo under your periodic schedule and

report the maximum height ever reached, divided by the sum of all

growth rates. The classes automatically store your results in a csv file.

Obey the comments! Once you downloaded the code, please in each of the

5 BambooX classes

add your vital username in the appropriate variable,

add your periodic schedule.

To compile the simulation, extract the zip archive to a folder and run javac

*java there. To run a simulation, use, e.g, java BambooUnequalPair .

Deliverables

Submissions are due 23 March on SAM.

This is an individual project; each student has to submit his or her own

solution comprising the following:

The 5 bamboo plot classes ( BambooX.java for each X in { UnequalPair ,

Fibonacci , Odds , Powers3 , Precision }),

the generated file with your results ( results.csv ) — Make sure you

have filled in your vital username!

A document describing how you arrived at the solution (not more

than two pages). Report also on dead ends you tried (what did not

work), as well as on arguments why a solution better than a certain

height is not possible.

2020/3/27 Programming Puzzle: Bamboo Trimming

The overall mark will consist of a weighted average.

40% for the description.

60% for the quality of the achieved solutions. The baseline are

solutions that George has found; in principle you could get more

than 100% for this subtask if you manage to beat his solutions!

Collaboration

This programming puzzle is mainly an individual project, and you have to

submit you own solution. In particular, the description of your solution

must be a single-author document.

Collaboration in small groups (not more than five students) on the

conceptual level(discussing ideas, not sharing entire solutions) are

accepted, but they must be declared in the description document, including

proper mention of others’ contributions.

Leaderboard

We run a (voluntary, anonymous) leaderboard of the current best solution.

Whenever you have a periodic schedule tried in the simulator, use the

below form to share your achievements with the rest of the class!

Bamboo trimming leaderboard

For each of the five bamboo plots listed below, you can enter the best ratio (as

output by the simulation) you were able to achieve.

* Required

vital user name *

Your answer

2020/3/27 Programming Puzzle: Bamboo Trimming

https://www.wild-inter.net/teaching/comp526/bamboo 5/8

Highscores

The plots below show all answers over time. Recall that lower is better.

New submissions are immediately added at the right end, but might take a

few seconds and refreshing before they show up.

ORCID: 0000-0002-6061-

9177

Google Scholar Profile

DBLP Publication List

arXiv Author ID

LinkedIn profile

Profile at UofL

(Old) website TU KL

sebawild at gmail ⋅ PGP

wild at liv.ac.uk ⋅ PGP

wild at uwaterloo.ca ⋅ PGP

wild at cs.uni-kl.de

Quick links:

my publications

my library

Sebastian Wild