Contest Analysis
Protein Contest Winners
Ever wondered about the MATLAB
contest winners? Who exactly is the lucky winner of that T-shirt that
should have been yours? Who is E. Brian Welch and why does he love hacking
our contests? No longer will they be just a name. Here we have given our
contest winners (and Brian), a little space to talk about themselves and
their contest experience.
MR Keenan
Grand Prize Winner
 Mike Keenan was born in Atlanta, Georgia, USA. He now works for Aspen Tech in Texas. Mike first started using MATLAB in 1986 when he was a chemical engineering PhD student at the University of Notre Dame. His thesis work was in the area of process control. Under the guidance of his advisor Jeff Kantor, they used MATLAB for all their controller designs and simulations.
At his current job, Mike develops model predictive controllers for use in a variety of industrial processes where a lot of the prototype development is done in MATLAB. About his contest experience, Mike writes:
During the Molecule contest, I came up with some of the algorithms that were an integral part of the winning entry, in particular a simple gradient search (greatly improved by Yi Cao who is some kind of MATLAB efficiency genius). Unfortunately, I didn't have as much time to during this contest to contribute.
At 4:30 pm on the final day, I was monitoring the queue. I noticed an entry by Claus Still and saw that he was trying an algorithm I hadn't seen before. I downloaded the entry and modified it so that it would run on my version of MATLAB. My jaw dropped when I saw how good it was. I made a few "tweaks" and posted a new version at 4:50, ten minutes before the queue closed. I named it Santa Claus in honor of Claus Still.
Amazingly, between 4:50 and 5:00 pm, no fewer than 7 other entries were posted nearly identical to mine. These folks had to seen my entry in the queue, tweaked it, and repost, all within 10 minutes. Luckily for me, all these entries were slightly slower.
In the last contest I was the victim of a tweaker and this time I got my revenge. I would like to thank Roger Stuckey, Lucio, and Claus Still for their contibutions to the winning effort. It is some very good work. I would also like to thank the MATLAB Contest Team for another great contest and for a superb problem selection. I am looking forward to the next one!
--MR Keenan
Nedialko Krouchev
Early Bird Prize: Best Entry at 3pm on Friday
 Nedialko Krouchev also goes by aliases JU and Justine depending on his percentage
contribution to the submission. Nedialko is from Bulgaria. He majored
in automated systems and control theory at the
Technical University of Sofia. There he completed his Ph.D. in
systems design by nonlinear, multi-objective and semi-infinite optimization.
He remembers developing a command line and expression interpreter
inspired by early contact with MATLAB available source code, then
written in FORTRAN.
More recently, Nedialko
is working at J.Kalaska's
System Neuroscience Lab at the Universite
de Montreal, Canada, pursuing his interest in applying engineering
and applied mathematics in the study of the brain. Some of
Nedialko's thoughts on the contest:
What keeps experienced professionals away from sleep,
food and probably their day job for periods of up to a week? It's certainly not the promise of a Rubik's
snake-puzzle. After I had been in three contests, this question demanded an answer. It's probably like
flying a plane in a model-aircraft competition. Competitors could be bank clerks or aircraft engineers, and
though the experience of the latter would certainly show, all would cherish the win. This "macho" feeling
is well described by a loose quote from the movie The Fast and the Furious: "If I win, I get your ...
respect."
There have been winners, but there has been no real conquest
of the always NP-full MATLAB contest problems. NP stands for non-polynomial,
and it means that the complexity of a problem of size N is expressed
for instance exponentially as M^N, instead of N^1 or N^2 (which
are some simple polynomials of N). It is the case in this contest
too, and the lowest M is 3, and the M suggested by the sample
solver is 4. Discrete mathematics problems are more often than
ever NP-full, and what better way of choosing one of them to keep
the tension high, up to the last minute of every contest. Because
the problem space may contain extrema in any location, you will
know that you solved the problem for sure only if your computer
was able to handle all the M^N variants, and an example that fits
well the hardest problems in the test suite yields 3^100 which
is ... 5.1537752073201133103646112976562e+47 variants! So here
you are on your own, against the odds and against the world who
is also your source of ideas and inspiration.
-- Nedialko Krouchev
Yuval Cohen
Early Bird Prize: Best Entry at 4pm on Friday
Yuval Cohen is the CTO and co-founder of Be4
Ltd located in Rehovot, Israel which specializes in 3D audio processing
algorithms. Though a physicist by education, Yuval has always been
an enthusiastic programmer. He first came across MATLAB, many years
ago. Today, MATLAB has become his primary development platform and
is used to develop algorithms that are embedded into consumer products. Yuval writes in his e-mail to us:
Other than MATLAB, my other fields of interest are carpentry, practical
shooting (pistol) and reading. My wife and I have a wonderful daughter
and I will start her MATLAB education as soon as she turns three.
This is the first MATLAB contest I took an active part in. I feel I won the early bird contest
by mistake, after tweaking previous code. My real contribution was writing Zigzag 2 and
the
permutator that works efficiently on short molecules and finds the best possible
solution by testing all the options.
I had another piece of code I was sitting on and planned to submit at the very last minute.
Unfortunately, thanks to my ISP, I could not access the internet during the last hour of the competition,
hence could not submit my code on time. That should teach me a lesson. It was pure fun and I learned a
lot. I wish TMW would conduct contests more often.
-- Yuval Cohen
Yi Cao
First Score to Break 2180
This is the second contest in a row in which Yi Cao has won an
early bird prize. Yi Cao who is currently a university lecturer
in the UK, has been using MATLAB for more than 10 years now. His
interests include math and computing. You might also remember some
of Yi Cao's entries in this contest causing problems with contest
machinery. Because of the global variable he used, many of the entries
further in the queue had to be re-scored. This took us several hours!
In his e-mail to us, Yi Cao has also provided us with some insight into how he played the
contest and his take on the "chaos" he caused in the scoring.
The submission that used global variables to store previous results
exposed a hole in the contest scoring program. This resulted in
contest chaos. Finally, I found a way using the minenergy function
(originally mine) to identify the contribution made by an individual
algorithm. Comparing with a profile report, I quickly spotted two
pieces of inefficient code. By removing these, the CPU time was
reduced significantly and the 2180 barrier has been smashed. I am
very glad to be a MATLAB contest winner again. I also wish to thank
all contestants who contributed to breaking the 2180 barrier.
It was also interesting to see so many successful cheating, spying and hacking
activities that parallelled the main contest. I am proud to have contributed to this.
The global variable hack comes from the idea that if the testsuit had identical proteins,
then we could save some CPU time by directly returning previously stored results. I
submitted code to store previous results in a set of global variables, however, this
submission proved that there were no identical proteins in the testsuit.
I then turned my attention to some other problems. However, on returning
to the contest scoring page, I was astounded to find that the CPU time of all
top entries were as little as a few seconds. I remembered the global code submitted
earlier and realized that I had found a hole. To demonstrate this, I submitted
several entries including
Hole? and Hole Demo!.
No one noticed this problem so I made a post to the newsgroup. Meanwhile, some contestants
started to manipulate the code to achieve lower scores. They submitted deep search code
with new global names to get a lower energy score with longer CPU time, followed by code
with the same global names to reduce CPU time. The contest scoring descended into chaos
and it took hours for the contest machinery to rescore the affected entries. The global
hole existed in all previous contests, however it was only in the Protein contest where
the pressure of CPU time led to its discovery.
-- Yi Cao
E. Brian Welch
Ph.D Student & Contest Hacker
Brian was
born in Nashville, Tennessee and did he undergraduate work at the
University of Southern California.
He is currently a graduate student in medical imaging at the
Mayo Clinic in Rochester,
Minnesota. Brian first started using MATLAB his freshman year in a biomedical
engineering class project and later on for several other courses. It wasn't
till entering graduate school that MATLAB became a day-to-day tool for completing homework.
In his Ph.D research, Brian works on methods to correct the image
artifacts caused by patient motion during an MRI scan. He codes
all his correction algorithms in MATLAB first because of its great
interactivity, absence of wasted compile time, portability, and
ease of debugging. MATLAB is also used to plot and display results.
Most of the figures I include in abstracts, presentations, and manuscripts
are created in MATLAB. Besides his graduate studies, Brian is also
interested in optimization algorithms and cryptography. He enjoys
playing volleyball and spending time with his wife, Yanice. Here's
Brian's Contest Story:
The first MATLAB
contest I knew about was the one on gene sequencing. I excitedly
joined in with some legitimate entries, but as the leading algorithms
became more complicated and harder to keep up with, my mind began
to wander as I thought about ways to achieve the best score... in
other words, how to cheat!
After some time I realized that the FINDSTR function, which was used in the contest machinery
to check if every ACTG segment was in fact in the returned solution string, does not care which
of the inputs is the longer string. So I submitted an entry returning only a single letter such
as "A" if it appeared in all the segments. Once I saw my entry with the big red one next to it
with an impossibly good score, I was hooked.
It's been my goal in every MATLAB contest since to find new holes.
In the Mastermind contest, I used the MLOCK to try to get more free
guesses, but I managed only to derail the queue for a few hours.
I wasn't able to participate in the Molecule Contest, but I was
able to return to cheat twice in this Protein Folding' contest.
The first cheat happened as I tried to sneak some non-Manhattan grid turns past the contest
machinery and realized that the 180 degree turns would pass as long as they're abs() was within
eps of 1. The turns were consistent enough to all equate to one, but unique enough within
floating point error to get past the UNIQUE function. The second cheat was a last ditch effort
after the official end of the contest where I used the ASSIGNIN function to set a loop variable 'k'
in the contest machinery to a high number to make the loop break such that my entry skipped all
the testing and got a great score. I heard from the MathWorks team that they tried to plug the
ASSIGNIN hole after spotting my entry in the queue. Fortunately the fix didn't go through as
planned, and I got to see my name next to the big red one again! ... at least temporarily.
So now I know I'm on their radar screen as an incorrigible hacker.
I may have to start submitting entries under an alias in order to
avoid scrutiny. It is getting more and more difficult to find holes,
but I promise that I will keep trying.
--E. Brian Welch
|
