Pi is still stuck in his life raft with Richard Parker, the tiger he (without thinking very carefully about it) managed to save after the ship they were on sunk. Now, for obvious reasons, he has to catch enough fish to keep Richard Parker full enough not to consider other options for food.Just as we enter the story, Pi has been lucky. He has caught a lot of fish which he keeps in a net trailing the little raft, which is attached to the actual life raft that Richard Parker occupies. He has also observed birds (meaning that land is not so far away), so he hopes that within the next three days, he will be saved.
Richard Parker can eat 60 kg of fish during these three days, and amazingly enough Pi has caught much more than that. So, he can also pay attention to other issues. From his many months with Richard Parker, he has intimate knowledge of Richard Parker's preferences when it comes to different types of fish. He knows this so well that he can associate an "enjoyment index" with each type of fish. To maximize his chances of staying alive, Pi wants to maximize Richard Parker's total enjoyment under the restriction that it can eat at most 60 kg of fish. Obviously, the wild beast will never stop once it has started eating a fish, so when Pi serves it a fish, it will eat it all.
The problem is now to help Pi plan the perfect selection of fish for Richard Parker. Thus, we must choose a subset of the fish such that the sum of their weights are at most 60 kg and the sum of the enjoyment indexes is maximized.
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.