Darkness 2002-11-05 00:00:00 UTC
Twilight 2002-11-06 00:00:00 UTC
Daylight 2002-11-07 00:00:00 UTC
Finish 2002-11-12 00:00:00 UTC

Protein Folding - 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