UCT Algorithm Circle

After much grinding away, we had our first class of the UCT Algorithm Circle this past Thursday. We invited 32 of the most talented school kids we could find in the Cape Town area and invited them to some training. We're also slowly inviting kids outside of Cape Town to train online. We're teaching them from the very basics of programming right through to the advanced algorithms and data structures required for the IOI.

For the first class, we introduced the basics of Python. We were amazed at how quickly the kids caught on. After a 20 minute lecture and 60 minute practical session they were understanding operations, variables, stdio and more. The majority of these kids are in grades 9 and 10, and amazingly half are girls.

If things continue at the rate they're going now, this could provide a serious boost to our IOI results in upcoming years. We've always been welcome to the idea of training a wider audience, but finding the talented kids and getting them interested has always been a brick wall we couldn't knock down. This time though, collaboration with one of the people involved in the teaching kids for the IMO has seriously helped change all that.

To see the kids we have, just check out some of their introductions in this thread to see what they're capable of.

Prototype

After completing the meat of my background chapter in December, I spent the most part of January working on a prototype for my masters project. So now I get to start showing off all my pretty pictures. :)

First of all, I should mention that I am writing an extension for VMD, so I most certainly did not develop what you see below from the ground up. In an effort to simplify the process of porting my work to other molecular visualisation applications (e.g. PyMol), I decided to do all the core computation in an application-independent C++ module which communicates with an application-specific plugin via sockets. For VMD, this plugin is written in Tcl, which I have come to hate.

When you first launch VMD, you get a simple protein. Launch my extension and it churns away, calculating conservation scores (dummy values for now) and the solvent accessible surface of the protein. The protein is then coloured based on the conservation scores, which you can see below for a sample protein.


After visualising the conservation scores, the final application will visualise its prediction of binding sites. The user will then be given the option of doing further analysis of the binding sites. We're currently considering two forms of analysis: select a residue and predict what a binding site containining this residue would look like; and select some residues and predict what the binding sites would look like if we excluded these residues from the predicted binding sites. Below is a sample of user-selected residues (in red).


Then the user can choose to visualise the solvent accessible surface. We calculate this surface using marching tetrahedra to extract an isosurface and kd-trees to calculate the isovalues. The surface is coloured by the conservation scores, just like in the previous shots. Currently I don't have residue selection working in this mode, although I plan on doing so. The meat of my computation will be using the conservation scores and the solvent accessible surface to predict the binding sites.


Then finally, VMD is a very feature-full tool and least of which you can do is rotate the protein for a view of the entire protein as you can see below. There is much more you can do with it, but I'll leave interested readers to explore themselves.


Next week I'm off to the Afrigraph Conference in Pretoria, after which I have to attend this 6 week bioinformatics course in Stellenbosch. Lectures 09:00-18:00 every day for 6 weeks. Not sure how I'm going to last.

Planning for PhD

After the painful experience of seeing my masters supervisor resign a few months ago, things have been turning out rather nicely. A huge advantage of working with my new supervisor is that she has good international collaboration. Last month I met the lead developer (from Illinois) of VMD, one of the visualisation programs I'll be writing my masters project for. This week it got even better!

This week, Dr Robert Best is visiting from Cambridge. It is looking increasingly more likely as time passes that he will be my PhD supervisor. Yes, that is correct...I am this close to getting the amazing opportunity of studying my PhD at Cambridge! The only hurdle at the moment is funding. I've been very slowly releasing news of this, as I first got word of the possibility around the time I started my new masters project a couple months ago. This is entirely thanks to my masters supervisor, Michelle Kuttel, who put me in contact with Dr Best.

Yesterday I met him for the first time, and we discussed potential research topics. The deadline for applications is due very soon, so for the moment we're focussing on a particular topic that looks very promising. Summarising very crudely, it's about taking advantage of both the speed of coarse-grained simulations and the accuracy of fine-grained simulations to produce fast, but accurate simulations of biomolecules. The main question here is how to swap between different representations of the system. Another possibility we have been looking into is furthering his research in reaction coordinates, which he summarises on his website.

By the way, this is the reason I am trying to finish my masters in a year. The year starts in October at Cambridge, and starting when their year begins makes things much simpler.

Proposal Presentation

My proposal presentation went really well today. I was concerned that the biology jargon would get in the way of the meat of the project, but we got past that. Edwin is my second reader and he provided some very useful criticism. Main thing I'm glad about is he suggested we remove the user testing aspect, which was always my least favourite. He also picked up a few bits of jargon we need to describe better come the thesis, but nothing major. The last thing he picked on was a concern I raised with Alex (my co-supervisor) previously anyway, which means I'll be paying more attention to it.

So on from here we go. Next step is to continue with the background reading and starting of the background chapter. The plan is to wrap up with the bulk of the background reading by the end of this year and then dig deep into the project. I have a tight schedule as I plan to finish up by October next year. I've had very contradictory reactions to this, some saying it's quite doable, others laughing it off. We'll see.

Masters Milestone #1: Proposal

If official milestones were all that counted, I'd be about to exceed progress of the project I previously spent six months on within the first six weeks of my new project. My proposal is all written up, gone through the shredding of two wild supervisors and I'm ready to present it to the department this Wednesday. Woohoo!!

It's insane thinking how fast things can move when everything just works. From the way things ran in my last project to this now, wow how things can change over such a short period of time. I have to thank my supervisors Michelle and Alex, they've really provided great support.

So anyway, Wednesday 13:00 in CS303. My title is "Development and Validation of a Visualization Tool for Predicting Protein-Protein Interfaces". If you're interested in scientific applications of Computer Science, this is a good example. It also involves quite a bit of computer graphics.

Juniors in the South African Computer Olympiad

A concern I have always had with the South African Computer Olympiad (SACO) is the lack of juniors (grades 10 and below) making it through to the third round and eventually the International Olympiad in Informatics (IOI). A glance at the SACO winner archive makes this quite evident. The only person that has won a medal in grade 9 or below (and hence stood a chance of making the IOI) was the well-known Bruce Merry.

Why do we have this problem? The obvious problem is that IT is only offered from grade 10 and it's nearly impossible for someone to pick up enough within those first few months in time to make the final round of the SACO. However, it is quite common to get those who taught themselves programming in the earlier grades yet only make the final round in there last one or two years. Vastly different situation to the Maths camp, where grade 8s and 9s are a common occurence.

Today we made a giant step in improving the situation. It goes back to little over a year ago during the final round of last year's SACO. We had three juniors (grades 8-10) joining us on-site for a junior competition in which they couldn't win anything. One of these kids did so well on the first day we invited him to write the senior paper the following day. Unfortunately as he only had a single day's worth of points to stand on, it was near impossible for him to win a medal and a place in the IOI training squad.

This gave us reason to invite a larger number to participate in the training. Due to a strictly worded rule, only the medallists could compete for a place in the IOI. Along with this and our limited budget we had to place several restrictions on those outside the top six, but we invited the next six best non-matrics to attend the training camps of which five accepted the offer. Things ran very well as the larger squad resulted in more discussion as well as pushed the top guys to perform better. Yet still, there was this lack of competition amongst those we called the squad++ as they had nothing to aim for but goals they set themselves.

For this year's final round the rule in questioned was worded more openly. The final round this year was the most competative from recent years and yet we still ended up with a new grade 9 and new grade 10 just missing the medal positions! It's been a long month, but today they were finally accepted into our first ever larger-than-usual squad. We now have ten highly competative kids in our squad, with the distribution being three grade 12, five grade 11, one grade 10 and one grade 9. All are elegbile to make the IOI team next year, and should Charl who's the one in grade 9 make the team he will be our youngest team member after Bruce! Now that they've shown us what they can do it's up to us to train them and make sure we continue to work on the great results.

I have some other plans to further increase the junior numbers. Now that we have these guys as role models it will be easier to catch the attention of other juniors and I don't plan on missing this opportunity. I already have the names of some current very capable grade 8s and 9s wanting to take a shot at the SACO next year. It's going to be a fun and interesting year to come!

ACM ICPC South African 2008

Yesterday UCT hosted 22 teams from UCT, Stellenbosch and UWC for the ACM International Collegiate Programming Contest. This year we had three new helpers from this years World Finals team that can no longer compete. We did a lot of preparation on our side for the event, but as we had the SACO just two weeks ago we didn't contribute any problems.

The contestants started arriving from 07:30 for a large breakfast we prepared for them. They thoroughly enjoyed all the food and chowed it far quicker than we could've imagined! Thanks to Chris Parker and Bertus Labuschagne for preparing the breakfast and snacks during the contest.



While the contestants ate and I handled registrations, Ian Tunbridge was in charge of preparing the lab with the team flags and balloons. For the first time we decided to blow up all the balloons in advance. Given the number of problems solved last year this seemed like a good idea, but alas as you'll find out soon enough it was not.


At 08:30 we started moving the contestants down to the lab, let them login and waited for the practice contest to start. After the practice contest the Nigerian server went offline due to power cuts, which pushed the start 45 minutes late. The start wasn't as pretty as we had hoped for, but things finally got underway at around 09:45. It took some time for the first problem to be solved, so I had plenty time to catch a before shot:


We put together a large team of UCT students no longer eligible to compete. We had Timothy, Migael, Tamara, Harry, James, Robert, myself and for a brief period Ian. Our first goal was to check the problems and send in any clarification requests early, our second goal was to beat Bruce who was doing them solo. Unfortunately we failed at our second goal, but then again Bruce cheated. :P We got A, B and D within little over an hour. We then got stuck for quite some time trying to match what was actually expected in F but got it eventually. Harry was working on C, but very quickly hit a dead-end as he was getting wrong answer. We asked numerous clarification requests and submitted countless times before finally getting it correct. We tried too hard on E, realising too late that a brute force solution would work in time (Bruce beat us to it and solved all six!).

This was our team near the beginning, minus me who took the photo:


More than an hour into the competition, ʇlnɐɟƃ3s got the first problem at the UCT site:


Things never really took off for the full five hours. The number of problems solved was very low with only 14 of about 70 teams solving anything at all, only two of them solving more than two problems. Going into the last hour Tuks3 were leading on time and the scoreboard stopped updating. This is when the local teams started pulling away, with team ʇlnɐɟƃ3s solving a third, followed shortly by Code Red from Stellenbosch also solving a third. At this point both teams were extremely close on time, but UCT's ʇlnɐɟƃ3s was just ahead.

It was in the last 15 minutes that ʇlnɐɟƃ3s closed the door on everyone else by solving their fourth and final problem. No-one was able to pass them in the final minutes. The end results were:

1. ʇlnɐɟƃ3s of UCT (Keegan Carruthers-Smith, Max Rabkin, Saadiq Moolla)
2. Code Red of Stellenbosch (Ralf Kistner, Dirk-B Coetzee, Petrus Theron)
3. Tuks3 of Pretoria
4. Team LOL of UCT (Julian Kenwood, Richard Baxter, Mike Talbot)
5. OMG Raptors of UKZN

With only 15 problems solved at the UCT site (23 overall) we had 117 inflated balloons left over. What to do with 117 balloons? Well we let the contestants take them home, and this was the result :)


After the contest we went to Primi Piatti in Cavendish for lunch. Unfortunately before we could go we needed to clean up the mess the contestants left behind. Yes messy bunch...Once the lab was all cleared up we headed off and were just about the last to arrive.


After lunch, which was staggered by table for some reason (the kitchen couldn't handle the numbers or something) we had a little awards ceremony.

3rd at UCT site and 4th overall: Team LOL (Richard, Mike, Julian)

2nd overall: Code Red (Dirk-B, Petrus, Ralf)

1st overall: ʇlnɐɟƃ3s (Saadiq, Keegan, Max)

Contest helpers: Marco, Harry, Timothy, Tamara, Migael
Missing: Chris, Bertus, Ian

Problems, detailed standings, statistics and more are available here.