main page — COMP 526 Applied Algorithmics

Programming Puzzle: Bamboo Trimming

**
This is an archived version of this module from Spring 2020.
**
Click here for the current iteration.

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 cut down exactly one of your the bamboo plants each day, and you cut it right back to the roots.

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 $n$ bamboos with daily growth rates $g_1,\ldots,g_n$, we assume that after growing for $t$ days (without cutting), bamboo $i$ will have height $t\cdot g_i$. Right after you cut a bamboo, its height is 0, and so is the initial height of all bamboos at the beginning.

Writing $h_i(t)$ for the height of bamboo $i$ after $t$ days, and $c(t)$ the bamboo that you cut on day $t$, we obtain:

\[h_1(0) = h_2(0) = \cdots = h_n(0) = 0;\] \[h_i(t+1) = \begin{cases} g_i & \text{if } c(t) = i \\ h_i(t) + g_i & \text{otherwise} \end{cases}\qquad (t\ge 0).\]The task is to find an infinite schedule of cuts $c : \mathbb N_0 \to [n]$ that keeps the maximal height $\sup_{t\in\mathbb N} \max_{i\in[n]} h_i(t)$ as low as possible.

To simplify your planning, you decide to restrict your attention to
*periodic* schedules, i.e., a fixed, finite list $C$ 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]

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:

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.

### Grading

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!

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