We hereby announce the competition Compiler of the Year.

The great tiger, Kitty, had trapped a large number of bachelor students in its cave. The students had thought that "Kitty" sounded so small and innocent that they had not worried too much about handling it. However, as it turned out, there was more to this "Kitty" than they had realized at first sight.

Anyway, Kitty now had a planning problem. There were simply more students in the cave than he could eat before they would go bad. He was figuring that he could eat about 600 kg of students during that time. He knew himself well enough to realize that once he started on a student, there would be no stopping until that student was completely consumed. So which students should he choose? Well, he decided that it would bring him the greatest pleasure to eat the most lazy students. Having observed the students for a while before the capture, he had estimated each student's laziness index. And, being an experienced hunter, he could estimate the weight of each victim to the gram! The formal definition of the problem was now clear to him: He should select the subset of students, weighing at most 600 kg in total, such that the sum of their laziness indexes was maximized!

With Kitty's solid background in Computer Science, he realized immediately that this was a computationally hard problem. To solve this to optimality before the food decayed, he definitely needed a program, and he needed someone to write it for him! (Let's be serious – tigers really cannot type with those huge paws.)

You could help Kitty by producing a compiler that generates fast code for the Knapsack program. (Or you could solve some other advanced task – Kitty 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 that 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.

 

---