nwerc 2007 and a laundry list

During the week-end that started on 17th of November I attended NWERC 2007 as a coach for the University College Dublin team O'Team: Rashid Bhamjee, Eugene Kenny, and Kirill Ignatiev.

Before the story, here's the blurb I sent to the students about this contest, in case you are not familiar with it.

The ACM ICPC is the oldest (1977) and one of the most prestigious algorithmic programing contests for college students. Approximately 1750 universities participate each year. This year's UCD team is: Eugene Kenny, Rashid Bhamjee, Kirill Ignatiev, and coach Radu Grigore. To the best of our knowledge this is the first time Ireland is represented!

The contest has two phases: regionals and the world finals. NWERC is the North-West European region, which includes Belgium, Denmark, Finland, Great Britain, Sweden, Ireland, Iceland, Luxembourg, The Netherlands, Norway, and West Germany.

The main sponsor of the event is IBM. On Saturday, contestants will go on a city tour (Utrecht), will attend a talk describing the Google File System, and will have a Google dinner. The complete program is available online.

On Friday evening we landed in Eindhoven, took a taxi to the train station, a train to Utrecht, and a bus to the University of Utrecht. We arrived 20 minutes before the registration closed. In fact, while I was solving e "Google brainteaser" I was told that the security guy wants to go home so I should turn off the computer. I got two questions wrong as far as I can tell, and there weren't many.

There I met Mihn Dihn, a.k.a. Minny. and he introduced me to other topcoders: starfrog, hungson175 (a.k.a. "The Healer"), jthread, Johan.de.Ruiter, and a few others. Mihn and Son invited us to play pool. Eventually Kirill and I decided not to go. Eugene and Rashid went to town until around 2am, then they tried to solve Rubik's cube and chatted for a couple of hours. At 7am we woke up because Saturday was a busy day. In the morning we attended a talk of ASML. These guys supply lots of the equipment used during the litography phase of building integrated circuits. The presentation was good. Although I don't like analogies to much you have to love this one: To get an idea of the scale we are working on I should tell you that we can print the map of Netherlads in 30 seconds, where each pixel represents an area the size of this microphone I'm speaking into. Then it went on to illustrate other challenges faced by programmers. These fall in two categories:

1. Software has to deal with everything that goes wrong in the other departaments.
2. The time needed to develop each new generation of the product grows exponentially and this can't continue.

Here is an example of a problem in the first category: If a laser beam goes thru a lens it gets hot and its optic properties change with temperature. These changes must be predicted (there is simply not enough time to measure) and adjustments done in real time, such as applying mechanical torque on the lens. As for the second problem, they think that the root cause is that the program is written in C. So the solution is to use higher level languages. In particular, they are collaborating with people in academia on automatically refactoring the existent codebase into something that unweaves aspects. Their vocabulary didn't even mention the words "high-level language" in fact, only "aspects". I'm yet unconvinced by the magical power of aspects to reduce interactions between pieces of code that are concerned with different things. But using MATLAB instead of C for numerical calculations sounds like a good idea, and I understand that error-recovery should be implemented in both MATLAB and C and it's not clear how to do it, hence you can label it as research in aspect oriented programming.

After that they presented the system used for judging and we had a test session. The problems were very easy, as expected. Here is an example: It is hard to solve integer equations algebraically and sometimes it's better to try a numeric solution. Consider the equation x^p+y^p=z^p. You must write a program that is given a nonnegative value p, less than 10⁹. If there is a solution with 0<x,y,z<10¹⁰⁰ then you should print such a solution; otherwise print "none".

Next comes the Utrecht walk, with a guide. I never had a guided tour of… anything. It was nice. They have a big church in the middle that was partly destroyed by a tornado. In fact, they have lots of churches and they also have something against churches. At least the guide did. They also have modern architecture, such as some university buildings, the mayor's house, and a strange tall metal house built on an 3 by 5 meters area at the corner of a street.

We then got back after having lunch (the sandwiches that Optiver provided were not enough for us. There we had a Google talk about the Google File System. The talk was quite entertaining but with not enough technical meat for my taste. If you read the paper you'll know basically all that we've been told (except the promises that our gmail is safely copied on many computers that Google engineers can access — that is, without the funny parts).

During the evening we played Mafia. I was killed during the second half of the game but I'm happy because I was able to take one of the mobsters with me while I was still a ghost. Before this we took a picture with lots of TopCoders (I believe that grotmol was the highest rated of us.) The picture is blurry, but I'll post it here once I manage to come to school once without forgetting the camera home. (It's harder than it sounds!)

At half past ten the honest citizens triumphed and we went to sleep.

Sunday was the fun day. I was quite nervous, maybe even more than my team. Anyway, they had this nice surprise for the coaches that they gave us computers and the ability to compete realtime. After I solved the easy problem I spent some time thinking about problem G (something with summits and a height map) and failed to solve it. There were at least three easy problems that could be solved: assemble, containers, and towerparking. O'Team only solved towerparking, beating five teams on time. That is an OK result for the first participation. My mistake: I focused too much on solving problems and not enough on their coding skills and on an emphasis on writing correct solutions.

Immediately after the end of the contest we had to hurry back to Eindhoven to catch a plane. I'll ask the three members of O'Team 2007 to guest blog with their thoughts about the contest.

In other news Mikolas, I, and Michal (sorry for the accents guys) got invited to submit a paper about reachability analysis for annotated code to a journal on software engineering. Here are some things we did or we plan to do for that paper:

• implement it in Boogie which is good for debugging the axioms of VerifiedC (Michal took care of this since he is now at Microsoft Research),
• implement it in Freeboogie (I'll do this),
• a better analysis of the algorithm used (see my previous posts that already hint at interesting links with standard problems such as building optimal alphabetic binary trees),
• make the ESC/Java implementation handle body-less methods (this was the number one request after the presentation at SAVCBS; we want to try at least three ways of doing it, one of which makes a cute use of counterexamples provided by the theorem prover Simplify),
• a better case study (we said in a few places that "we don't quite know what went wrong"), and
• better error reporting (give error traces a la Rustan, and guess categories of problems, such as "loop unrolling").