Computer Science Honours at UCT: Part 1

Today the 3rd years were given some presentations and the likes to try convince them into doing Computer Science honours next year. I was quite surprised to year the low number of only 68 3rd years there are this year, which can be compared to our number last year of about 110. To help make the decision easier for some, I'll start reviewing the modules we had on offer this year. These are only the first few - more to come later.

Research Methods (RM):

Combined with PCU (more later), RM is the only compulsory module for CS honours. In some ways I was unfortunate to have missed most of the lectures for this course (not by choice). Honours is the first year in which research is introduced and this course covers the basic research techniques. This year we were lectured by Edwin, however there appears to be a rotation strategy with this course. Of the lectures I did attend I picked up on some useful content. Our project proposals and literature review formed the mark for this module.

Professional Communication Unit (PCU):

Many people complain about PCU when they are forced to do it in third year. Some also did it in other courses. However, from the few lectures I attended (again, I missed most of them) I actually enjoyed the course. It was nothing at all like what we did in third year. We had several group discussions about matters such as formal meetings and many other things. There were fun group exercises which made the stretch of 4-5 consecutive lectures bearable.

An oral presentation done in pairs and an essay were the two assignments for the module. For the presentation you are recorded and have to watch all the recordings as a group. You get a dry run for which Terri really picks on everyone, but the comments are constructive and useful for the real presentation a week later. If you do NVP (see later) you don't have to do the essay as you do a business report for NVP which is then counted towards PCU. I did NVP and so never did the PCU essay.

New Venture Planning (NVP):

NVP is all about starting a business. The end goal is to produce a business plan in groups of four and give a presentation on the business. That's the assignment, and there is no exam. The lectures follow a discussion format and each one covers a different aspect of businesses from coming up with ideas to financial statements. It can be interesting if you are considering ever starting your own company, however, given the choice again I wouldn't take it.

The business plan is roughly 30 pages and you build on it throughout the course. Jonathan, the lecturer, gives some good feedback on the drafts. To get an idea of what it's like, you can see my group's business plan here. Warning: the idea we (I) knew wouldn't work all along, but we Jonathan liked the idea and we convinced him it would work! As you might have guessed, he is not a Computer Scientist in any way.

IFIP Summer School:

This might not be offered next year, but if it is it's very worthwhile attending. You go to Gordon's Bay for a week of talks by nine speakers covering a wide diversity of topics. Interesting topics this year included Stochastic Pi-Calculus (biological programming language, which while sounds scary was actually very interesting) and Pattern Recognition and Machine Learning (by Christopher Bishop - the lead researcher in the field!).

The assignment for this module was scrapped since it was as insane amount of work. The assignment (and exam) was set by University of Pretoria and there was obviously a misunderstanding about the workload. The exam was therefore the graded work for this module, but it was bad enough. It was a ten hour take-home exam in which we had to writeup in a very hand-wavy manner on three of the nine topics. The exam was really silly in my opinion and it spoilt the wonderful talks. I would strongly recommend attending, however without taking it for credit, i.e. no assignment/exam.

Advanced Computer Systems (ACS):

Don't let the name confuse you. This module covers advanced networking topics such as wireless networks and mesh networks. It's lectured by Kritzinger - I'll let you ponder that for yourself. Last year there was only one student that took the module, however this year we started out as nine. The first half of lectures covered basic probability theory and Markov theory. Kritzinger isn't very good on lecturing the basic statistics and so I would be cautious about taking the module if you don't have any stats background. If you enjoyed his third year course, however, you might want to consider taking it.

I only attended the lectures without taking it for credit, so didn't do the assignment/exam. The assignment was to take a research topic in networking such as ad hock networks and write a paper on it. The exam was a 15 minute oral exam which was apparently very easy.

Computer Graphics for Gaming (CGG):

An enjoyable course on introductory computer graphics. This course is (has) been consumed by the new gaming stream now offered at UCT. Since it will no longer be offered as an honours module from next year I feel it's pointless discussing further. However, I'd like to warn those going into second year that you will not be able to do any form of graphics if you don't take the gaming stream. And the advanced graphics module contains some very interesting stuff, especially if you're into your maths.

Network and Internetwork Security (NIS):

NIS covers some interesting topics in cryptography. However, I find it goes too deep into the protocols and not enough into the details of the actual cryptographic methods. It's a very high level overview of security in its current form, but a fair amount of the content should already be common knowledge.

The assignment is made out to sound very complex, however most people ended up doing very simple watered-down versions of one of the protocols. To give you an example our group covered DNS security and we easily got away with implementing what amounted to a dumb DNS server with a table mapping full domain names to an IP address. Of course security was added, so some of the important stuff was covered, but we weren't required to produce the hierarchy that's typical of DNS.

I would be 50-50 as to whether I'd choose this module given the choice again.

That should get you thinking if you're considering honours in Computer Science next year. Reviews of the remaining modules will come in later posts. The really interesting ones are still to come, so don't make your decision based on this post alone!

Part 2

ACM ICPC Registration

It's that time of year again. The ACM International Collegiate Programming Contest is fast approaching, with the Southern African regionals set to take place on the 20th October.


For UCT students, we've just opened up registration which for the first time is all done online (it's about time!). You can head on over to the following site for registration (remember, UCT only!):

http://people.cs.uct.ac.za/~mgallott/acm-icpc/register/

If you are at another university in Southern Africa, check the regional site for further information. If you want to participate, but are stuck finding who to contact at your university, drop a comment here and I'll try my best to help you out.

For those at UCT, we have arranged some special deals with Google which should make this year even more spectacular than ever before. As if being crushed by Bruce wasn't enough (remember last year?), how about being crushed by Bruce working together with a couple Google engineers? ;-) Ag, it's fun times. Even if you get 0, you'll still have a ball.

Remember that this is Bruce and Carl's last year with us (and likely to be my last one at UCT too), so make this one special for us. Let's get as many teams as we can. Let's show all the other universities we're competing against who's the best! A repeat of the top 5 at the IT Challenge would be amazing, but just as amazing would be getting 20 teams. :-P

The world finals are in Canada next year, hosted by the University of Alberta. The hotel looks simply amazing:

Facebook Programming

This month I delved deep into the big, evil mass that has somehow managed to attract so many millions in such a short time. I'm talking of Facebook.


In May this year they launched the Facebook Platform, an API for developers to develop their own applications that could integrate into Facebook. Most of you will better understand me if I simply referred to Facebook applications. Those things that many consider to have damaged Facebook beyond repair. Super Poke anyone?

There's a course on Internet Interoperability offered at UCT and I was contemplating whether or not to take it. When I discovered the assignment would be developing a Facebook application, however, I thought it could be an interesting experience. I don't think I would have investigated it on my own as I'm not all that interested, but since we were being taught on the topic I decided to take the course for fun.

The code for an application is hosted by the developer and Facebook queries the developer's server when the application is accessed by a user. For scalability purposes, the profile box is generated only by the application only when a user takes an action such as configuring th application. The generated FBML (more on that later) is stored by Facebook to provide pseudo-dynamic content that when is already there when a user views the application on a profile.

A developer codes up several pages, such as the installation page, the dashboard and the main application page. Each can interact with Facebook by sending and retrieving data using its REST-based API. The API offers a SQL-like query language called FQL to retrieve specific data, while this is all retrievable by other API calls. The code then outputs FBML (Facebook Markup Language) which is a subset of HTML with some Facebook-specific tags, such as fb:name, which are translated into HTML by Facebook. When code on the developer server is called, the code can set the FBML of the profile box.

There's a lot more to developing an application, but that's the basics. One of the major hassles I found is the numerous small things you had to do to come up with a complete application. There are so many pages, some of which they could easily offer template pages for, such as invitations, installation, etc. The other hassle was the number of round-trips between the application and Facebook servers very easily caused timeouts. Bear in mind the awful latencies between South Africa and the rest of the world!

If you're wondering what application I developed, it's a simple application which gathers publications from OAI feeds. It lets you select and display a list of your publications. It's not polished at all, so I wouldn't call it very useful. I used it myself to just experiment around with Facebook applications. If you really want to check it out, it's available here.

After all that, we also wrote an essay on the interoperability of Facebook. It was a fairly interesting topic, but it was a little restrictive on the content. You can grab mine here. I'd be interested to hear what other Facebook developers think.

IOI Photos

I've gathered all the photos our team took and have made them available here. Still waiting to get from two more and I'll add them when I do.

This is my first time using Picasa and I must say it's very useful. It's also available for Linux.

IOI Results

The results of IOI 2007 are out. Tomasz Kulczyński of Poland won with a total of 574/600 with two Chinese trailing behind him followed by a Croatian. We got two bronze medals with Ralf just missing out on silver by two places (6 points) and Dirk-B making the other end of bronze.

The results are available in full here. Henadzi Karatkevich of Belarus won the youngest medalist award - winning a gold (20th place) at the age of 13! Chinese once again got four golds.

Dirk-B receiving his bronze:


Ralf receiving his medal:


The full team after the awards ceremony (Donald, Marco, Mark, Dirk-B, Ralf, Charles, Peter):


All is over now. Tomorrow we catch a 10:00 bus to the airport. It's been a wonderful time, even with the few criticisms. I'd love to return to Egypt next year, which from speaking around looks like could be an amazing year.

IOI Excursion: Plitvice Lakes

Yesterday was the main excursion day at the IOI. The main part of the excursion was visiting the Plitvice Lakes, after which we visited the Nikola Tesla Memorial Center. The Plitvice Lakes are part of UNESCO's world heritage and is apparently the most famous national park in Croatia.

There were two groups of buses, with the first leaving at 06:30 and ours leaving at a more reasonable 08:30. It was a long bus ride as the park was 140km out of Zagreb. We finally got moving at 09:00 and arrived two hours later. Before catching the bus we had breakfast. When we arrived they gave us a packet of yet more food!

The park was very beautiful. It was overcast for most of the time and even rained for short periods, but that didn't detract from the beauty too much. After walking a little, everyone gathered around to board the ferries. Unfortunately we were near the back and all the ferries were full. We were told that it would take two hours before we could catch a ferry, so we took their recommendation and walked.


There was a lovely path following the edge of the lake which we took. We got to see lovely views of the lake and surrounding mountains. I would say it turned out best that we walked instead of taking the ferry. It took quite a bit longer, although the wait for the ferry would have made the ferry option take longer. Along the way we saw several types of unusual mushrooms and other wonderful sites.


After about 90 minutes we caught up with the rest of the group that had taken the ferry. This is when we discovered that the plan was for us to wait those two hours for the ferry. Most of the people we met up with there were from the 06:30 bus and this meant we had gone through the route too quickly. So we took a detour and went to see some of the waterfalls. Unfortunately we never got to see the main waterfall, but apparently there's not too drastic a difference.

After the waterfall Dirk challenged Ralf to some rock climbing which he accepted. He didn't get too far, but at there were no unwanted injuries. I say that because one of the other contestants apparently cut himself, although I'm not sure how bad it was. It always happens!




After the waterfall and monkey acts, we rejoined the main group to catch the ferry back to the entrance. It started raining a little while we were waiting, but after the first lot of ferries were loaded we got a spot under the trees so we never got all that wet. There were two ferries we had to catch and we got back to the buses by 15:00, the time we were told to be there. The problem was that we were about the only ones there. All the others were still walking around the park - late!

The other teams came in very slow drips and drabs and we ended up waiting for more than 90 minutes. Most of that time we spent outside the bus in the fresh air, however the time we spent in the bus waiting for the thing to move was painful as it was rather stuffy inside. The opportunity to see those wonderful lakes was well worth it though, but the organisation could have been improved a great deal. We were supposed to be back at our accommodation by 18:00 and it was already 16:30 with lots to still do. As time passed, the poor organisation became more and more evident. The guides were by no means the ones with which the blame lies as they were following the poor instructions given to them.


Once the bus finally moved, we were taken to what they called lunch, however it was already 16:45 by the time we arrived. We split into two restaurants as they weren't large enough. Donald and Peter chose turkey so they went off to another place while we had the pork option. The food was good.

After lunch we had to wait yet another half an hour for the buses to arrive, pick us up and start moving. By this time it was already about 18:30. We thought they would cut out the Telsa Center, however they were adamant that even though they were running well behind schedule they were going to take us there. The memorial center is in the very house he was born and lived in, out in the rural area of Croatia.

It was rather small and most of what they had was a timeline of Croatian history. They had a tesla coil, which is what Tesla is famous for inventing, however it wasn't powered on. I generally like most museums, but considering how far we had to go to get there, this place wasn't all that exciting. The youngsters spent more time in the rather interesting playground which had some unusual swings and other devices with which the guys had a ball with.


We left the place at about 21:00. One of the buses broke down along the way and the teams inside that one spread out amongst the remaining buses. Most of them had to stand in the buses as there weren't enough seats, which was expected. The journey back was very long and we finally arrived at our accommodation at about 23:30. I rushed to dinner before the queue started and was very lucky along with Mark and Dirk as by the time the others had thought about dinner the queue was very long.

There was a team leader's part schedule for 21:00-23:00. You can imagine, however, that they weren't able to stick to those times and so they started at about midnight. I went past, but there were very few there and some ran off to their own private parties and so I didn't stick around for long at all. An early night was in order and that's what I got.

This morning we had our final GA meeting. Amongst many other things, we voted for the new IC (International Committee) and ISC (International Scientific Committee) members. An Argentinian and Macedonian got the the two IC positions with a New Zealander missing out. A Polish and Mexican beat the Australian and Chinese that nominated themselves for the two ISC positions.

After the meeting we went out and did some shopping. At 17:00 this evening the medals are announced at the awards ceremony. While some people have compiled an unofficial list of some of the teams' scores here, nobody knows the medal cutoffs. It looks as though a Polish has won again and that the Chinese have got all golds once again.

IOI Competition Day 2

Today was the second day of competition and it's now all over. Now there's the anxious wait till the awards ceremony on Tuesday evening, with an excursion to the Plitvice Lakes tomorrow, which I've heard is going to be amazing.

Quick catch-up on the events since my last post. On Friday night we discovered that the room next door was not empty as we had originally thought. Rob Kolstad was in it. He stuffed up with his flights and booked to arrive a day late. Anyway, he's one of those people that just knows how to talk, and talk. Between Rob and Donald our early night turned into a late night, 3 hours of chatting about life stories later. It was enjoyable though.

Yesterday we had an excursion to the Jarun Lake. It was a nice break from the usual environment and although it was overcast when we arrived, the sun came out later on which made things rather pleasant. There wasn't much to actually do there besides relax and chat with the other teams, but it was great. Now's a good time to mention just how much they try feeding us. We had brunch at the lake, which followed an early breakfast. Then when we returned, we still had lunch and then dinner later on! And it's all fairly decent for such an event.

One of the New Zealand contestants borrowing Charles' juggling balls at the lake:


After lunch we took another tour of the city. Unfortunately the shops closed at 15:30, so we didn't have much shopping time. However, we had a wonderful time seeing more of the city. One thing I really love about most European cities is the rich history. Zagreb's not excluded by any means!


After the tour of the city, it was time to wish the team good luck and go over to the GA meeting to go through the second and final problem set. This time I had Brian Deen from America sitting next to me and we went through the problems together. Miners was an easy DP. Pairs requires a 3D range tree, which can be compressed into a 2D range tree. Quad trees should also work for most test cases. Training was a very nasty graph theory problem involving even cycles. The problems, test data and official solutions have been released here.

There weren't any major concerns with the problems, except that it was requested the them of Pairs change from what it was initially. The English was a little poorer for this second set of problems, but it was dealt with well and much more efficiently than the first round. The atmosphere was as good as always. We were out of the translation room by 23:00.


The next morning when we went for breakfast, we were pleased to find that the quarantine issues from before had been ironed out and there was no repeat this time. While the contestants wrote the second round, we once completed the second half of the IOI Conference. Once again, some very interesting talks by some countries which we will have to analyse in more detail and learn from their experiences.

After the conference we waited for the team to return. The initial look on their faces wasn't that excited, but they thought they had faired reasonably well. Some ended up pleasantly surprised with their scores, while others a bit disappointed. For all but one of them this is their last IOI. After lunch the scores were waiting for us, which was very impressive. We got 2 triple digit scores and two double digits. I'll let out the real scores after the awards ceremony on Tuesday. Bruce back home on the online contest has impressed once again though. He got the max!! That's all their is to say really.

We had a meeting with Rob after the analysis phase on the possibility of creating a team event for the future, but I'll leave the details to a later post. There was also a very long GA meeting during which lots happened, but details in later post. Just one thing worth noting is some statistics on mark distribution per problem:


Aliens: 50 full scores
Flood: 24 full scores
Sails: 12 full scores
Miners: 131 full scores
Pairs: 9 full scores
Training: 3 full scores

So, watch out for more on those two meetings and our trip to the lakes tomorrow!