Competition

Shere Khan has had the good fortune of trapping a large group of monkeys in a cave. He's very familiar with all of these monkeys since they always tease him and throw coconuts after him. In fact, he maintains a nuisance index for each monkey, expressing precisely how annoying each of them are. Now Shere Khan has the following problem. He really prefers live prey, but he has trapped many more monkeys than he can eat. From experience, he knows that during the next couple days before the monkeys die of thirst, he can eat exactly 600 kg. As soon as Shere Khan smells blood, he cannot stop eating, so if the starts eating a monkey, he will eat it up completely. In other words, it is entirely inconceivable that he would eat half a monkey.

Your task is to help Shere Khan plan the perfect meal before that irritating man cub, Mowgli, shows up and burns his tail. In other words, you must help select a subset of the monkeys, maximizing the sum of their nuisance indices under the constraint that their total weight is at most 600 kg. The program Knapsack solves this problem, but as already explained, the result must be computed as fast as at all possible. This is your task!

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.