Saturday, May 31, 2008

UCT Computer Science Test/Exam Archive

It's exam time at UCT once again, but thank goodness I'm not writing any longer. I've kept an archive of past tests, exams and other related things on my website going back to about 2001. There are a lot of holes, which I try fill whenever I find someone will papers lying around.

I've just done a bit of updating of 1st and 2nd year papers. Currently it's sitting at about 50MB, which should give you an idea of how large a collection it is. Lots of people have found it very useful. I just hate it when some lecturers are so indecisive as to whether to give them to the students and that by the time they do it's just too late. It's also miserable the number of test and exam questions that are blatantly copied over the years.

Peruse the archive, take from it what you wish and please send me any papers you find that I'm missing:

http://people.cs.uct.ac.za/~mgallott/?id=19

Friday, May 30, 2008

China Booked

So I finally decided to go to RoboCup in China at my own expense, along with three of our lecturers and three other students. We're almost settled on flights and accommodation, although we still need to pay next week. We also need to sort out visas, which might be slightly problematic for me considering I went to the Italian Consulate to apply for a new passport when it was looking like we weren't going to China (they only take 10-15 days though).

We're flying with Emirates, departing on 11 July. We're in Suzhou until 21 July when we head back and stopover in Dubai for 3 nights, returning to Cape Town on the 25th. The trip is actually pretty reasonable, coming to about R11,000 for flights and accommodation.

21 days after we return, I hop back on the plane to Egypt for the IOI!

Suzhou, China

Dubai, UAE

Sunday, May 25, 2008

South African IOI Team 2008

Three weeks ago we had our final training camp before selecting the South African team for the International Olympiad in Informatics. We experimented with extending it by a day to allow for more presentations and have group problem tackling sessions, which worked out really well.

Shortly after the camp we had a meeting to select the team. The team for this year's International Olympiad in Informatics in Egypt is:

  1. Haroon Moolla
  2. Mark Danoher
  3. Saadiq Moolla
  4. Schalk-Willem Krüger
Yes, Haroon and Saadiq are brothers, which is a first for the South African team. It is also a first that we have two members from the same school, which I am proud to say is my school -- Rondebosch Boys' High School. No, I did not rig the results. ;-) In fact the two that lost out on being selected were also from Rondebosch!! What is also great to see is that Schalk-Willem is only in grade 11 and so therefore has the opportunity to attend three IOI's.

The IOI this year takes place in Cairo from 16-23 August. I will be attending as deputy team leader along with the team leader Peter Waker.

The second round of the SACO takes place at schools across the country in just 5 days (30 May). If you're one of the contestants be sure to read this page I wrote for information on how to prepare.

Internet Problem Solving Contest

The 10th Internet Problem Solving Contest (IPSC) took place yesterday afternoon. This is the third year I've participated in and it always proves to be a great contest with some original problems. This year was no different!

I got several teams together at the University of Cape Town and we gathered in a lab together for the contest. We had ten teams participate in the lab and a few doing it from other locations. As Bruce was taking part, no-one stood any chance to pass him as the top South African team. Unfortunately for us though, things were looking worse as he managed to team up with Paul Jeffreys who won the IOI the year I took part!

It was still lots of fun, nonetheless, and I must say I was rather impressed with the team that beat us by four points. Yes my two team members did leave an hour early, but they were ahead of us long before. The final standings for our local teams is available here:

http://olympiad.cs.uct.ac.za/training/standings240508.html

There was one unsolved problem, which was really insane. It asked you to determine the expected cost of the minimum spanning tree given that the edge weights were uniform random variables each with their own lower- and upper-bounds. Solutions to the problems are available here.

African Intercollegiate Programming Contest

At the ACM ICPC World Finals in Canada earlier this year I met the two other African teams and we discussed the possibility of hosting an ACM-like contest for African students. A considerable amount has happened since then, to the point where I'm starting to have discussions with sponsors.



There are about eight teams from North Africa that participated in their ACM regional contest. The top team came very close to beating our top team at the world finals, after five years of us pretty much dominating. There are also a few other African countries looking at sending teams to the IOI. The aim of this contest is to bring together Africa's top talent and put them up against one another. This will hopefully provide a more interesting challenge than our usual contests within South Africa, which are on a much lower level than the current next step up, international competition.

NVIDIA have offered to donate graphics cards as prizes and I'm meeting with two people from BSG early next week to discuss their potential involvement. If there are any other potential sponsors reading this post, please contact me privately (marco AT gallotta DOT co DOT za) and I will send you a proposal. This has a lot of potential to attract some really top students across Africa so I feel it's a great sponsoring opportunity.

If you're a student in Africa, watch this space for further details. I will be trying to spread the word to get interested universities shortly.

RoboCup Update

It's been a while since I last posted here, mostly because the quick mini-blogs in Twitter are far less time-consuming. However, it's about time I gathered the important updates into one post so here goes.

Some of you have been following my progress with my applications to study masters in the US. Since my last update three of them were no's with two remaining. About two months ago I got a negative response from UIUC, which ended the possibility of going to the US. The only one that remained, Waterloo, was taking it's time and I heard from some Canadians that their universities take considerably longer to respond. I have still not yet heard anything from them.

After all was basically lost and only Waterloo remaining, I made a tough decision. I was enjoying the work I was doing on RoboCup and three others were making a masters degree of it. So I decided to cut my losses with Waterloo and start studying towards a masters degree at UCT. The work I had been doing purely as a filler became my masters topic. Many people have been asking about what happened -- there's your answer.

I made that decision in late March. Nine weeks have passed since then and we've grown into a team of 1 honours, 5 masters and 1 doctorate student, not including our German and Austrian counterparts. My field within RoboCup is the localisation of the robots. In simple terms, localisation is about taking input from the various internal sensors and camera images to determine the position and orientation of the robot on the field. It involves a lot of statistics, which I majored in, and some image processing.

Some specifics on the problem I'm tackling. First of all, the robots have only a 500MHz processor, which is shared between all modules (intelligence, motion, kinematics, odometry, stability, image processing, etc.) and considering we have to process in realtime this is a real challenge. The playing field is well-defined, with the colours of objects chosen purposefully to make the image processing task easier. The lighting in many leagues is very well-defined as well, however, this is not the case in our league where the lighting could vary drastically between matches. In all other leagues in previous years (this is the first time our league is running) they've had uniquely coloured beacons to help with localisation. For this league, they are completely removing them, making localisation a far more complex task. All we have now are the coloured goals and the white field lines.

The approach that I am researching into is based on Monte Carlo Localisation (MCL). I have read up many other approaches, most notably the Extended Kalman Localisation, but they aren't as well suited to the specific problem I am solving. Some particular issues include the kidnapped robot problem (when the robot is moved by the referee, can localisation readjust itself?) and the non-unique classification of a field line segment seen to an area on the field (which part of the field line are you looking at?). One issue with MCL is that the more sampling you do the better the results, but as we're limited in processing power we can't sample more than about 100 points.

We've been having quite an issue with finding funding. It was looking good early on, but many of the sponsors want to see results before giving anything and to get results we need to be given. Wonderful catch 22 situation, which has resulted in many problems. It's looking as though our individual funding will go through very shortly, which is good news.

There's also been a serious issue with the development of the robots. This is a standard platform league so all the robots are supplied by the same company. They're commercial robots which will go on sale in 2010 and we're getting prototypes. Unfortunately they are falling behind schedule so teams only got sent a single beta robot, but only those who had paid. Yet the German's who were handling the funding and purchase of our robots haven't yet been able to sort it out due to some complications such as the German government not being sent an invoice for the robots, we have still not received any robots.

When word came out that we were only expecting to receive the robots by the end of June, three weeks before leaving for China, we promptly decided not to go to China. There was already all the fuss over it potentially not being held in China at all and the complaints from other teams that the robots were breaking down. Enough was enough! When we had a closer look at the agreement though, we realised we were contracted to participate. We have only three weeks with the robots, no funding and the robots are breaking, yet we have to participate...oh wonders!

The final call made by our supervisors was that the three of them would travel to China at their own expense. Graeme, our RoboCup supervisor, would go as our team leader, Stephen would go to suss out the RoboCup Rescue league which he will enter next year and Anet, our CS supervisor, would go to meet our team members from Germany and Austria. They then told us that we were welcome to join, but at our own expense. Two of us decided to go and three decided not to. The other two of us (me included) were (and still are) sitting on the fence and need to make a decision by tomorrow!

Well, that should give you all enough to sit on for now. It's a lot of happenings squished into such a short space. Let me just end with our amazing logo, which has a whole story behind it on its own:


and our website:

http://www.ibots.uct.ac.za/