After the curtains of Ice Age 4, Captain Gutt recovers and once again becomes a threat to Manny and his family; particularly to Peaches of whom Manny is still rather overprotective. The pirates renewed strength stems from economic capabilities due to an enormous treasure they acquired. This enables them to purchase the newest weapon technology the ice age has to offer.The "herd" decides to go for a financial attack to protect Peaches and the rest of the herd. The saber-toothed tiger[1] Diego and his new girlfriend, Shira, plan an attack on the pirates. Their idea is to approach the pirate ship from sea at night while the hyraxes distract anyone who might wake up. For this purpose, Manny and his family construct a ship that can approach very quietly and which has a cargo capacity of 600 kg., in addition to the crew.
To hit the pirates as hard as possible, they must quickly move up to 600 kg. of the most valuable items from the pirate ship to their vessel, before they quickly and quietly disappear into the night. Ellie, being the brains in the family, realizes that this is computationally hard, and they need a really well-constructed program to do this optimally. Having no computer scientist in the family, the only one they can think of turning to is Scrat, but based on our experience with him, I really hope you can do a better job!
You could help Diego by producing a compiler that generates fast code for the
Knapsackprogram in/home/IMADA/courses/cc. Or you could solve some other advanced task – Diego would actually be pleased and potentially reward efforts in any direction.
Unfortunately, the prize of this competition is not impressive. Actually, if you win, I'm afraid your reaction might be that "all I got was this lousy T-shirt..." As usual, the judges of the activity will be as fair as possible in deciding who wins the prize...
The compilers will be run on publicly available programs
(note that a program such as OutOfBounds is bugged;
thus, here the correct runtime behavior is to return the
correct error code)
as well as on further tests.
Additionally, the compilers
will be exposed to a time trial of the generated
code for the program, Knapsack, as well as other programs
of different flavors.
Finally, we will evaluate the extent of additions that improve
on other aspects such as ease of programming in your language, space
utilization, and other elements.
We make a combined evaluation of the correctness, efficiency, and features of the compilers (and possibly extended language). Correctness has highest priority in the sense that there is a limit to how many errors the compiler can make before everything else becomes uninteresting. Efficiency and other features have equal weight. Thus, focusing on speed (and the time trial) is neither an advantage nor a disadvantage.
Our evaluation will lead to the selection of the Compiler of the Year. The winner group will be announced on the course home page. As mentioned, there will be a small prize, but you are primarily competing for the honor.
If you want to make extensions that are time-consuming at
runtime (runtime checks for out-of-bounds, etc.),
you may equip your compiler with the ability to recognize an option
-x such that as default your compiler runs with the
time-consuming code, but with an option, these can be
deactivated. Then we will use this option
during the time trial.
The evaluation is made immediately after your compiler code is turned
in, i.e., before we see the report.
Together with the compiler code, you may turn in a document called
claims.pdf. The purpose is to assist us in making sure
we notice all the wonderful things you have done. ツ
The first page should contain an itemized list of extra achievements.
You may include descriptions of the different topics in the
following pages that we may refer to. However, do not waste precious
time on this; if you include extra descriptions, just use (drafts of)
what you would put in the report anyway.