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:
- Software has to deal with everything that goes wrong in the
other departaments.
- 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
xp+yp=zp. You must write a
program that is given a nonnegative value p, less than 109.
If there is a solution with 0<x,y,z<10100 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").
Posts
