Teaching Blog About
! main page — COMP 526 Applied Algorithmics Programming Puzzle: Bamboo
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?
Copyright By PowCoder代写 加微信 powcoder
You will be working on a real, challenging research problem, so the intention is as much on practicing 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 and your partner are passionate gardeners, 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 both decide to cut down exactly one of your
the bamboo plants each day, (so 2 plants in total per 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 g1 , … , gn , we assume that after growing for t days (without cutting), bamboo i will have height t ⋅ gi . Right after you cut a bamboo, its height is 0, and so is the initial height of all bamboos at the beginning.
Writing hi (t) for the height of bamboo i after t days, and c1 (t) resp. c2 (t) the bamboo that you and your partner cut on day t, we obtain:
h1(0) = h2(0) = ⋯ = hn(0) = 0;
hi (t + 1) = gi if c1 (t) = i ∨ c2 (t) = i (t ≥ 0).
{ hi (t) + gi otherwise
The task is to find an infinite schedule of cuts c : N0 → [n] × [n] (where c(t) = (c1 (t), c2 (t)))
that keeps the maximal height supt∈N maxi∈[n] hi(t) as low as possible.
To simplify your planning, you decide to restrict your attention to periodic schedules: You specify a fixed, finite list C of pairs of cuts to execute, and when you are done with this list, you simply start from the beginning again, and repeat this process indefinitely.
Your garden contains five named bamboo plots with the growth rates of the bamboos given below:
1. 2. 3. 4. 5.
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 Python implementation of the bamboo-trimming problem that you can use to evaluate your trimming schedules:
▸ Python sources
There is one file bambooX.py 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. The classes automatically store your results in a csv file. To run the simulation, extract the zip archive to a folder and run, e.g., python3 bambooInequality.py there.
Obey the comments! Once you downloaded the code, in each of the bamboo*.py files, add your periodic schedule to list queue .
Deliverables
This is an individual project; each student has to submit their own solution. The submission is on Canvas, split into the following parts; you have to submit all of them.
Note further that only typed solutions will be marked, but you can use any format that Canvas accepts.
Part 1: Your written report of how you arrived at your schedules
(not more than one page)
Describe any systematic approaches you used (if applicable) and also report on dead ends you tried (what did not work). Structure your writing with sections. A secondary criterion here is simplicity of the solution: If you cannot seem to improve the heights, extra marks can be awarded for the simplest solution that achieves that solution quality.
Part 2: The quality of your solutions and code
1. smallest height you could achieve for all bamboo plots
2. heighest lower bound for the height you could prove impossible for all
bamboo plots
The overall mark will consist of a weighted average:
▸ 20% for the report.
▸ 50% for the quality of the achieved solutions. The baseline are solutions that Ben
has found; in principle you could get more than 100% for this subtask if you
manage to beat his solutions!
▸ 30% for the lower bound proofs.
Collaboration
This programming puzzle is an individual project, and you have to submit you own solution. In particular, the description of your solution must be a single-author document. As for all assessments, the University of Liverpool Policy on Academic Integrity applies; please refer to the Canvas page for details.
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 solutions. Whenever you have a periodic schedule tried in the simulator, use form below to share your achievements with the rest of the class!
Bamboo trimming leaderboard
For each of the bamboo plots listed below, you can enter the best maximal height (as output by the simulation) you were able to achieve.
(未分享) 切换帐号 *必填
vital user name * 您的回答
Inequality
提交 清除表单内容 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.
Equals: [10, 10, 10, 10, 5, 5, 5, 5, 5, 5, 5, 5]
Inequality: [98, 98, 1, 1, 1, 1]
Split: [100, 32, 16, 8, 4, 2, 1, 1]
Power: [96,54,54,48,24,18,18,12,6,6,6,3,3,2,2,2] Fibonacci: [55, 34, 21, 13, 8, 5, 3, 2, 1, 1]
a zip file with all your Python scripts (the bamboo*.py files) Part 3: Your lower-bounds proofs.
For each lower bound from the previous question, describe why this height is impossible to achieve (by any schedule) in the given bamboo plot.
Your answer should have one section for each bamboo plot. Each section should contain a concise proof of why this height is not achievable.
▸ sebawild at gmail ⋅ PGP
▸ wild at liv.ac.uk ⋅ PGP
▸ wild at uwaterloo.ca ⋅ PGP
▸ wild at cs.uni-kl.de
▸ Website at UoL
▸ intranet site at UoL
▸ TCS @ Liverpool
▸ (Old) website TU KL
Elsewhere:
▸ GitHub profile ▸ LinkedIn profile
▸ ORCID: 0000-0002-6061-9177 ▸ Google Scholar profile
▸ DBLP publication list
▸ Semantic Scholar Author Page ▸ arXiv Author ID
Quick links:
▸ my publications
▸ my library
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com