Tony, the tiger, has managed to break into a Kellogg's samples storage room late a Friday afternoon. It is awfully hungry, but also pays significant attention to the enjoyment of its meals. Tony figures that it will have all weekend before it's discovered. During that time, it's capable of eating 600 kg of cereal. There are many different boxes of cereal with different weights and different flavors. Tony eats a box in one mouthful, so a box is either eaten completely or not at all. It doesn't like all flavors equally much (for instance, it really really likes Frosties), so with each box, Tony associates an "enjoyment index". Thus, each box has a weight and an enjoyment index.The problem is now to help Tony plan the perfect weekend. This means that we must choose a subset of the boxes such that the sum of their weights are at most 600 kg and the sum of the enjoyment indexes are maximized. The program Knapsack, written in the programming language Tony, solves this problem, and Tony would really wish that it would execute quickly so he can start eating. If only someone could provide a compiler that would generate efficient code for this program...
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.