Renewed Masters

It's been two months now since I heard the news that would result in drastic changes in my life. I never realised just how bad the news was that day. It took some time to sink in. When it did, however, that was the start of a very stressful period for me. I'm talking about the day my supervisor resigned.

There's a lot of details behind what happened, but for personal and ethical reasons I have chosen not to comment about it much online. It is for the same reason I have held off posting about what has been happening until now. Now that things are settling down it's time to start coming out with the news though. Many of my friends have known about this for a while now, it's just time I announce it publically.

So my supervisor resigned. Within a couple days I started talking around and within a week I was discussing the possibility of a new project. Ironically the first person I spoke to, Michelle Kuttel, is now my new supervisor. The main reason for the change of topic is that no-one else at UCT was strongly grounded in the field of my existing project. While it meant essentially writing off six months of hard work, I had to consider my long-term goals. It sucks, it really really sucks...but I don't regret making the decision, not yet. It's been a long, stressful ordeal, but I feel I've made a good decision.

My new project is in bioinformatics and is on protein-protein interface prediction. It's a graphics-heavy project with the new field of computational biology to learn. It's a drastic change from my previous project, but I have reasons for doing so. The plan is to get down to serious work quickly and get wrap up end of September 2009. It's a very quick masters, but after the huge setback I'm seriously determined to get this done and with my supervisor believing it's possible I will get it done.

Apologies for keeping this so brief, but I don't want to say too much publically about this. You'll be hearing more about my new topic though, no reason to keep that quiet! I plan on putting together my proposal by the beginning on next month and giving my proposal presentation a week or so after.

South Africa Google Gadget Competition

Google are starting a Google Gadget competition in South Africa, pitting UCT up against Wits. Here's another chance for us to show our dominance at UCT. The competition was first run in East Africa, and now we're getting the next one. The prize includes a trip to the Google engineering office in Zurich for a dinner with the Google SA team.

Gadgets are interactive mini applications built using HTML, with JavaScript, Flash or Silverlight for dynamic behaviours that live inside a web page. Think of them as Facebook applications that can be used on any web page. Practically anyone can add a gadget to a website they have built, but many are used on iGoogle. Millions of people worldwide use iGoogle every day. Just look at the collection of existing gadgets ranging from a simple clock to the Google Talk gadget. More info is available here.

David Harper from Google is giving a presentation of the competition at UCT on Thursday 24 July (date and venue TBD). The other important dates are:

July 21, 2008	Registration open
August 15, 2008	Registration close
August – October, 2008	Students build gadgets
October 31, 2008	Gadget submissions due
Mid-November 2008	Winners announced

I've created a Facebook group which you should join to discuss the competition further if it catches your interest:

http://www.facebook.com/group.php?gid=18095983733

Some more info directly from Google:

We're looking for the next generation of gadget developers in South Africa and to reward the university in South Africa where outstanding creativity meets state-of-the-art technical skills. This year we will have one university in Johannesburg and one university in Cape Town compete against each other.

Students who wish to participate to the contest will register and submit their ideas for what they think will make a great gadget from July 21st through the submission form below. Each proposal should explain what the gadget does, who would use it, and why it will be successful, as well as adding some details about how the gadget will work.

Students will then have until October 31st to work on creating the gadget. The deadline for submitting a fully-functioning gadget is October 31st. We'll communicate the link through which students can submit their gadgets at a later point in time.

After the deadline a committee, composed of Google engineers as well as some preeminent tech personalities from South Africa, will judge the gadgets.

The overall winner together with some runners up will win some of the following prizes: A trip to Google engineering offices in Zurich, Switzerland, dinner with Google SA team, visibility and PR. All will receive an iGoogle gadget certificate.

The winning university will be publicly announced by Google and will also receive an iGoogle gadget certificate.

If you have some technical skills, and are enrolled in a Bachelor's, Master's, or PhD course in 2008 at the University of Cape Town or the University of Witwatersrand in Johannesburg, we would love to hear your gadget ideas. Please submit your gadget idea through the registration form below.

Refining Masters Topic

One thing I have come to learn very quickly is that what they say about masters (and research in general) being a continuous refinement of your research topic cannot be more true. If you had told me two months ago that my topic would be thinned down to what it is today I simply would not have believed you!

When I first approached my supervisor, Anet, about joining the RoboCup team I saw it as just that, an opportunity to help in putting together an intelligent system for a robotic soccer team to compete in RoboCup. And I was going to be doing the vision and localisation. My oh my, how that vision (excuse the pun) has changed.

First of all, I am no longer doing any vision-related work so my reliance on Patrick Marais as co-supervisor has fallen away. I dropped it because, to do anything novel to any degree (while masters does not require this, they try get it from you here) I had to concentrate on a narrower topic, which in my case was localisation.

Then lets look at RoboCup. Well the initial aim was to ship a prototype for the RoboCup tournament in July. If I was to have done that though, I simply would have had insufficient time to do enough reading and that would result in me wasting a lot of time essentially being a code monkey hacking away at something that would certainly not be novel and, given more time to read up on and design, would be fairly trivial. Then there's also the major problem that we simply have not yet received any robots yet!!! This just makes development of anything on the robots a lot harder and frankly I'd rather wait until we get them before doing any hacking as we might realise things we cannot know without seeing the robots. Then there's the fact that one of our team members in Austria, Christof Rath, is already working on basic localisation for July.

So we've realised that we don't get much (any?) credit from RoboCup directly. The traditional (for want of a less offensive term) folks of this world don't see RoboCup as being real research so we have to target it as a more general solution for robotics in general and tag RoboCup as simply a testbed. It's a very neat testbed though, as everything is already laid out so there's a lot less of this topic refinement I'm talking about in this post. Most masters projects typically start out weakly defined with huge scope and can even change completely over the course of the project. We simply don't have that problem, which is great as we can focus from much earlier on.

Another area of refinement, one which I briefly touched on above, is that of supervisors. Anet Potgieter was always my main supervisor from the get go as she started the local RoboCup initiative. Anet's research field is agents (subset of AI). She's so busy though: over 20 graduate students, 10 honours students and the director of a company!! Then we needed a co-supervisor in mechanical engineering: I chose Stephen Marais who's doing his PhD in SLAM (Simultaneous Localisation and Mapping: a problem more difficult than localisation on its own) and he's been great as he's always in and his office is right in our lab, even though he's really on sabbatical. Then I started out with Patrick Marais as the computer vision guru at UCT, but since I dropped that part I no longer have him as co-supervisor. Then finally, just a week ago I approached one of our newer lecturers Hanh Le and she jumped at the opportunity to co-supervise me. She's viscuous, but in a positive way. She refuses to accept students unless she knows they are top students and looks far ahead, much further than most other supervisors do. Still early to comment too much, but to give you an idea she gave me a wad of papers 15 cm tall at our second meeting! And for completeness, my second reader is Edwin Blake.

So anyway, the reason I started out with this post was that I am at the final stages of writing up my research proposal. It's done, just needs to go through final checks. The deadline is six months after starting, I've almost got it out after two so I'm already ahead of schedule. :-D The aim is to have my proposal presentation on Wednesday 2 July so if you're in the area and would like to attend (if you're not a UCT student you should ask before coming as attendance might be restricted, I'm not 100% sure), watch my blog for further details. The aim is to put my presentation together with that of Andre Scholtz who's doing the collaborative intelligence for RoboCup.

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

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/

Google Student Ambassador Programme

A couple of days ago I received an email from a university programs coordinator at Google about the Google Student Ambassador Programme they are launching in Africa and the Middle East. One student is selected from a university as the student ambassador and his role is responsible for representing Google at his university. This involves organising Google-sponsored events and handing out Google goodies. One of their popular things they like to do is organise pizza for the other students during exams and other deadlines when people are pulling all-nighters.

The requirements of the job are pretty standard:

• Student in Computer Science or related field
• 2nd or 3rd year undergraduate or graduate-level student
• Excellent academic performance (equivalent to an A- mean grade or above)
• One-year commitment
• Active in university student community
• Passion for technology, innovation and learning

But not the benefits :P :

• Leadership role
• Exposure for your university at Google
• Free food
• Google gear
• Admiration from your CS peers

It's a small step, but an interesting one I find. Very often companies approach the staff as an entrance point into universities, but not with Google. Yes, they did have a series of meetings one day with our staff, but they have made a far greater effort in approaching the students directly. Is it necessarily a good thing though? Well, it is unusual and that alone gives it a chance of working. But in many cases students just aren't interested in this sort of thing.

Is the fact that they are just Google going to make this work? Would it work for any other company? My feeling is that it very much depends on the company and its culture. NVIDIA, for example, has the right culture to make a strong student-company relationship work as well. I was actually trying to discuss this very sort of relationship with them towards the end of my internship. I think it also requires that the student has an active interest in the company, such as I do in Google.

If you are interested in applying (and you are a UCT student) then let me know and I can recommend you to Google. I found some further information on the program here and you can also read the email below. This is definitely a step forwards, but I hope it moves further.

The full email I received:

Dear Marco,

I hope this email finds you well.

We wanted to get in touch with regards to a Google Student Ambassador Programme we have just launched for students enrolled at universities in Middle East and Africa.

The Google Student Ambassador Programme, an exciting new opportunity open to high-achieving technical students at select universities in Middle East and Africa.

Google Student Ambassadors are the voice of Google on university campuses and work with Google to plan and implement university events, which promote information technology, Google products, and student learning.

Ambassadors act as a technical resource amongst their fellow students and a university liaison for Google. Students who participate in this programme become part of an international network of students dedicated to improving knowledge transfer between industry and academia.

One student per university is chosen to serve for the duration of the academic year, after which they'll receive an official certificate in recognition of their achievements and contributions in this role. While the responsibilities associated with this position are a considerable time commitment, they are also a fun way to learn more about Google and give back to the university community.

Being a former intern we believe you know Google, our culture and products very well and could make you a very good ambassador.

We have just launched the programme and are currently soliciting details of interested students to whom we will reach out with more information about how to apply to become a Google Student Ambassador by March 10th, 2008. I wanted to get in touch with you before though to see whether you would be interested in applying for the programme.

If you can't commit, maybe you know fellow students that you could refer?

The requirements for becoming an Ambassador are:

• Student in Computer Science or related field
• 2nd or 3rd year undergraduate or graduate-level student
• Excellent academic performance (equivalent to an A- mean grade or above)
• One-year commitment
• Active in university student community
• Passion for technology, innovation and learning

If you can think of someone who would make a great ambassador, please do not hesitate to send me their contact details and we will reach out to them with further details by March 10th, 2008.

Please let me know should you have any questions in the meantime.

We look forward to hearing from you.

Best regards,

Maria

They're Running Out!

From Princeton:

Dear Mr. Gallotta:

Thank you for applying to our Graduate School for the 2008-2009 academic year. While I assure you that the materials you submitted were carefully reviewed by the faculty in the Department of Computer Science and by the Graduate School, I regret to inform you that the department did not recommend your admission for the coming year.

The number of places available at Princeton for entering graduate students is extremely limited and we cannot offer admission to all who are well-qualified. Indeed, many departments consistently have applicants who would be admitted without hesitation if the resources were available. Our decisions take into account not only the applicants’ merits, but also the suitability of the department’s programs to the candidates’ expressed interests. Our goal is to achieve a sound match between the strengths of our programs and the interests of the relatively small number of outstanding students that can be accommodated.

We chose to advise you of our decision via email on the assumption that a timely response would outweigh the informality of this means of communication. I would be happy to provide a formal letter upon request.

I wish you success in your plans for graduate study and thank you for considering Princeton University.

Sincerely,

William B. Russel

Dean of the Graduate School

So, only two places left: UIUC an Waterloo. And UIUC is the one I really wanted!

It Won't Be The Bay Area For Me

This just in from UC Berkeley:

I regret to inform you that you have not been accepted for graduate study in Electrical Engineering and Computer Sciences at the University of California, Berkeley.

The Berkeley campus has a strict enrollment ceiling and thus each department is limited in the number of new students it may admit each year. Our department has the difficult task of selecting students with the strongest overall records from a large pool of well-qualified applicants. Unfortunately, this means we are not able to offer admission to many applicants who are capable of excellent academic work.

I am sorry that we do not have a place for you and hope that you will be able to make other arrangements to achieve your academic goals.

Sincerely,

Joe Hellerstein, Vice Chair
EECS Graduate Matters

I'm not sure how wide-spread this his, but a friend tells me he hasn't heard of any South African being accepted by more than two US universities. I can only hope this is the reason I am getting all these negative responses back.

One Down, Four To Go

Just a couple of hours ago, the following hit my inbox:

February 11, 2007

Dear Marco Franco Antonio Gallotta,

Thank you for applying to the Computer Science Ph.D. Program at Stanford University. The Ph.D. Admissions Committee has reviewed your application and we are sorry to inform you that the committee did not recommend you for admission. The number of applicants far exceeds the number of those we can admit, which makes the admissions process a difficult and painstaking one. As a result, many strong candidates must be turned down.

We wish you every success in satisfying your educational and career goals.

Sincerely yours,

Graduate Admissions
Computer Science Department
Stanford University

I'm not sure what my response is to it yet, but it's sinking in fast. This is a big step I'm taking, one which will decide my future for at least the next five years. And now that that the first response has come in, I'm starting to feel very nervous as the rest are likely to start coming through rather soon now. Nervous as hell! I just want it to be over, either way!

The Honours Year

Today I completed my honours degree. Four years at UCT, completed! Provided nothing goes ridiculously pear shaped I will be awarded my second degree next month.

It's a strange feeling, partly due to the uncertainty over what I will be doing next year. I have applied to study further in the U.S., however, I will only find out if I'm accepted some time in March. If I get accepted into one of the places I have applied to I will be starting a MSc/PhD there in September. If I get rejected (oh no!), however, my plans are to start an MSc at UCT and then push hard to get into a PhD overseas. Even if I do get accepted what I'm doing between February and September isn't finalised, although I do have some potential plans. So I might return to UCT for some time, I might not return at all!

Honours has been the first real year of studying in my opinion. Computer Science undergrad is way too easy, especially when you enter it already having a good background in programming. This has been the first year we have really gotten to know the lecturers. It is the first year we have had our own personal lab. It is the first year we have had the choice of modules It is the first year we had a major project. All these things add up to a most enjoyable year. Most importantly though is the size of the class. With only 37 of us, all having made it through undergrad and remained, this has been the first year I have really gotten to know the entire class. Knowing that most of the class will not be returning next year and that some of them I will never see again makes it a rather sad time.

It has been an exciting time. I truly believe that the honours year is worth more than the three years of undergrad combined. I would strongly recommend it to anyone wondering whether they should continue after graduating with their BSc. An honours is what distinguishes you from the masses.

So that is it. It is over. No more. Done.

Next up -- Nvidia! I finally had my appointment at the US Embassy yesterday and received my H-3 visa this afternoon. I have my flights booked -- 29 hours each way! I have sorted out accommodation at Greenpoint Apartments. Chris de Kadt has just finished his own internship there this week and so he has offered me his furniture and other stuff which has helped a lot! Apparently they pass on furniture between interns there. So I am all ready to leave on Saturday evening and start working Monday morning!

Sorry Janis, but I have to share what you said me as it was classic! This is what she (management person at Greenpoint) sent me this morning:

I had to call my husband who was in the marines to find out what the heck 16:00-17:00 was. Welcome to California we deal in the "o'clock version".

Honours is Over!

Today has been a day to remember. A wonderful year has ended today. Yes, today was the final day of my honours degree. It is over!! Some will consider it a happy moment, but I consider it a sad one.

Lots to do though. Going for pancakes for my farewell since I leave on Saturday. More about this later!

UCT Deputy Registrar's Dark Past Uncovered

A little over than two months ago, Dr Paul Ngobeni was appointed deputy registrar at UCT. Now usually I'd be completely disinterested with changes in UCT staff, let alone the legal positions. However, two weeks ago news that he had been previously suspended from practising law in the US 18 months ago was revealed.


Two weeks ago this article was published, which appears to be what broke the news to the public. The whole thing goes back to December 2005 when he was indefinitely suspended from the practice of law in Connecticut after he failed to appear for a presentment hearing. The list of offences goes on and on and are outlined in that article in greater detail.

It was this article that got me to post about this though. He apparently claimed that the whole thing was a "smear campaign by some whites," because "news of his difficulties emerged only after he jumped to the defence of embattled Cape Judge President John Hlophe." The article where he defends Hlophe can be read here. Notice that that article was published on October 17 and that the article revealing his suspension was published on October 23. So it's not impossible that this had some impact.

Lets take a step back for a moment. How was it that UCT employed Ngobeni before doing a thorough background check? Any reasonable check should have resulted in at least some of this background of his being discovered. When will be the day when one at least does a simple two minute Google search? If you haven't clicked on that link I suggest you do. The rankings may well have changed over the past couple weeks, however, I can guarantee you that this one was right on top. That was in fact the very page that was the first lead that resulted in the search for more information on Ngobeni.

How do I know this? That would be due to me knowing the people that dug up Ngobeni's past -- Ben Steenhuisen and Laing Lourens. The thing that I wanted to point out, however, is that it was identified before Ngobeni's article on Hlophe on October 17. This flat-out nullifies Ngobeni's pathetic decision to stand behind such a weak attack that, even if it was true that it spurred the interest to search for incriminating evidence then so what? Once you've voiced such a strong opinion then you're only attracting attention that will always result in at least some people wanting to find out more about you!

And then there is this:

Ngobeni said he did not have to inform UCT of the charges and convictions before his appointment, as it was public knowledge, and had been published on the internet.

No, seriously man? That's all I can take of this.

Digg
Reddit
Muti

Computer Science Honours at UCT: Part 3

This is part 3 in my review of the CS honours modules at UCT. Read after reading part 1 and part 2.

Distributed Computing (DC):

There's confusion over the name of this module. It is often referred to as Distributed Components -- the notes say Components, but the official name is Computing. It's lectured by Ken and well, yes, it's not the most thrilling lectures you will attend. I just attended lectures, but never took it for credits so I skipped the assignment and exam. There is so much theory that is covered in this module. It's all thrown at you in huge chunks and it's not easy to consume. Most of the class take DC, but I'd be hesitant to recommend it. It's too much of this RPC stuff such as Corba and DCOM and then stuff on COM+, .Net and EJBs.

The assignment was on EJBs and I remember everyone scrambling to figure out how to get JBoss and EJBs to work! For those of you doing it next year, Sean posted some HOWTOs which seemed to be very useful. Ken, as in the past, kept pushing the deadline back and the demos were only done last month (for a first quarter module)!! Now this may sound cool, but it's not when you consider that it ends up interfering with the other assignments. Last year he never marked it -- everyone who handed in got 100%. The exam was apparently rather hand-wavy. So, up to you, but I don't recommend taking it.

Interaction Design (ID):

What is CS at UCT without lectures by Gary? He's simply the best at lecturing in the department, no doubt about it. I would usually be completely deterred from an HCI course as I find it mostly fud, but I could never miss a Gary lecture. He goes into all sorts of things to consider when designing an interface and shows cool video clips that keep you interested and add to the lectures.

This is another course I only took the lectures for and nothing else, and I think it was a good decision. Most of the class take this module, but unless you're good with design (and I'm not!) the assignment and exam are finicky. The assignment was about building a paper prototype for an RFID tag reader for a cell phone. You then had to implement a prototype that just simulated the interface without requiring functionality and write a report on it. The exam was apparently fairly decent and it's usually based on case studies, which means lots of writing.

Effective Virtual Environments (EVE):

EVE was an interesting module and I'm disappointed I had to drop it after two weeks. All the really good modules were run concurrently, which was a pity. EVE lectures are more like discussions on beliefs than lecturers -- the content covered is very much dependent on what the class finds interesting. It's taken by Edwin, who actually does a good job of the course. I was very surprised at the low numbers that took this module as I'd recommend it above other modules such as DC and NIS.

The course changes drastically year-on-year. Edwin tries to remove the need for an exam by pumping up the practical workload, although if the class prefers an exam he is willing to sway. This year there was one big assignment split into three and a essay on some papers. The assignment was about using Erlicht, a 3D games engine, to design a putt-putt course. The first part was a design document, which was fairly lengthy. Then you had to code it up using Erlicht and you were marked based on how closely your end product tied in with your design document. The final part was to test a hypothesis such as "Do textures increase presence?" You're told to get six test subjects, although you will never get a significant result with such a small number, so please get more people next year. It's not that difficult!

Databases (DB):

DB is lectured by Sonia and it is the only module for which I never attended a single lecture. That should sum up my interest in databases at such a level. The content is rather boring, although it's easy marks, mostly covering object relational databases such as Oracle. The class is usually fairly large, although I can't stand taking a module just for easy marks. Half the lectures were paper reviews presented in groups for marks. The exam is fairly easy apparently.

Can't say much more here, best speak to someone who did the module.

Computability and Complexity (CC):

Computer Science courses are very practical in nature, that's not going to change. However, I feel that it's necessary to break away a little. That's where the Mathematics of Computer Science modules come in. They're highly theoretical and have little practical application. You need a strong Mathematics background to get through these modules as not only is the content pretty tough, the pace is insane. Ever had a Maths lecture with slides? With CC, every lecture is based on slides - even the nasty proofs!

The module is lectured by Vasco Brattka, the best Maths lecturer I have ever had! He has a list of the course contents available here. He also has the course slides and tutorials there, but they are password protected. If you're considering the module then I can give you the password, although I'll have to do so privately. All the Maths modules are four credits, so they cover a lot of work. You get one period a week dedicated to discussing the tutorial questions before you have to attempt them. They can be tricky, although the help in lectures is decent.

The class is mixed with Computer Scientists and Mathematics honours students. This year only three of us CS students took the Maths modules along with two Maths students. The computability stuff can be scary for a Computer Scientists, especially when the Maths guys catch on fairly well. The module is packed with proofs, including some that were open standing problems for decades. The proofs in the complexity section are more algorithmic and so it switches around to the CS students understanding better. The module culminates in showing why the P-NP problem is so hard and that under certain assumptions is provable to be unprovable either way!

The exam is slightly easier than the tutorials, although it is closed book and therefore rather challenging. However, if your Maths background is strong it's not so bad. I would definitely recommend the module to anyone that majored in Maths. Since it's a four credit course it gives you more choice with what CS modules to pick from and lets you get away without doing the crappy assignments. I still attended many of the lectures for the other CS modules, although it's nice having the comfort of dropping out of the ugly ones.

Cryptography and Complexity (Crypto):

Vasco used to offer a Quantum Computing (QC) module, which expanded on the work from CC. However, he went on sabbatical for the second half of this year and so it was replaced by a new course. If QC returns next year, and it most likely will, it might replace this course. Although I never got to do QC, I've heard from previous years that it is very good and if CC is anything to go by I can believe it.

The new Crypto module was split in two parts covered by different lecturers. Christine Swart took the first half, covering topics on public key cryptography. There's a lot of number theory involved, so don't expect it to be like a CS module. It's fairly practical compared to the rest of the CS of Maths modules. You learn all about factorising very large numbers efficiently and showing that cracking the RSA algorithm is equivalent to factorising such numbers. The Diffie-Hellman key exchange is also covered and it's shown that cracking it is equivalent to the discrete logarithm problem.

Holger Spakowski takes the second half, covering topics related to complexity of cryptography. This section goes back to where Vasco left off in CC. It's all about probabilistic algorithms that can be proved to produce the correct answer with a given probability. From this the concept of probabilistic Turing machines are developed and this leads into a whole new area of complexity classes. This then leads into proving various classes equivalent to one another and a number of inclusion relations. It gets highly theoretical, although it's a great module for those interested in Mathematics and Statistics.

Christine was very bad with the tutorials and we only had one that was marked in the end. Holger gave us three, which were fairly challenging as a Computer Scientist. The exam is next month and since it's a new course I can't comment on it. Overall I would recommend the course. The cryptography section should appeal to a larger number of CS students than CC. The major problem with this course is that the second half continues into the project time. So while the rest of the CS class is enjoying no lectures to work on their projects you have to worry about tutorial hand-ins and so on.

Summary:

So I've summarised my experiences of the honours modules and given my comments for you. Make sure you've also read part 1 and part 2. Remember that this is just my thoughts on the modules and that I have very different interests to many people. If you're going into honours I expect you to take what I said with some common sense.

Take a look at the Graduate Handbook, especially the section on the modules as they provide module descriptions. Bear in mind that the modules on offer are likely to change next year, so don't go out of your way to settle on a selection. If you want to decide early try find out from Anet who will be the honours course convener next year and ask that person what the module list is looking like. You may also find that looking through my exam archive might help ease the decision.

Something that no-one mentioned to us last year and that I found critical was that your choice depends largely on the timetable. You can get our timetable here (with ITE added in at the same time as Agents, GA and II). As you'll see, many of the content-heavy courses such as DC, DB and ID are all grouped together at the same time, which makes it difficult to skip them all. I think the basic timetable remains the same each year, but make sure by asking the course convener.

The way I personally tackled the decision was just to attend all the lectures. For each module I attended at least a quarter of the lectures and by that time we usually got through enough to understand what the assignment involved. If the assignment looked icky, I dropped the course, otherwise I continued with it. It might sound like a lot of extra effort, but you're there for some lectures so you might as well just check the other maybes out. I found it worked really well as I got to choose given first hand experience of what the lectures were like. After four lecturers you generally get a gut feeling. You just have to make a rough selection at the beginning of the year, which can easily be changed any time by notifying your course convener.

So that's that! If anyone wants to chat further, I'm only around until mid-November. I'd be happy to have to discuss it though as it's a crucial decision. Very little word goes around about what the modules are like since most people ask so late. I might add another post on the honours project, but I need to know who would be interested? If you want to hear my thoughts on the project or anything else please let me know.

Grid-Based Genetic Algorithm Approach to Colour Image Segmentation

So, my honours project has reached completion status. Yesterday my partner, Keri Woods, and I demoed to our supervisor and second reader. Following the demo, our project went on display along with all the others in the department for our annual Computer Science Open Day.

I have a full project website, which you can check out here:

http://people.cs.uct.ac.za/~mgallott/honsproj/


The project was about using a genetic algorithm to solve the problem of colour image segmentation. There has been an abundance of research into image segmentation, but there is still no one true algorithm that solves the problem once and for all. Our aim was to see if it was possible to get as close to this one true algorithm by using a genetic algorithm to handle the uncertainty in the input.

A secondary aim was to develop a genetic algorithm model for the Grid. There has largely been a lack of research in this area and we attempted to spark some interest. Lots of research, especially testing on larger scales, needs to go into this before it is usable.

Check out the website if any of that catches your interest. I certainly enjoyed the project a lot and it's disappointing it's come to an end. I will probably still try make some time to put some further work into it.

Under vs Oversegmentation

I've started getting my first segmentation results for my honours project. To sum it up in a few words, image segmentation is about breaking an image up into regions. This has many applications and is often the first step in image processing, with the end results heavily relying on the segmentation quality.

The problem is that it's very difficult to define what a good segmentation is. It depends a lot on, amongst other things, the nature of the image. Lighting conditions, noise, texture - these can all have a large impact on the results. A key problem in segmentation is that of splitting up into too few (undersegmentation) or too many regions (oversegmentation). This is easily demonstrated by my first results as shown below.

The first image is the original we're trying to segment. It's the famous Lenna image used throughout image processing as the standard test image. Notice the noise in the background, texture in the hair and hat, smooth texture of the skin and many other features that one aims to handle well in image processing.


These next three images are segmentation results I obtained from my implementation of the Watershed algorithm. The first result comes out of the Watershed algorithm with no improvements to the original algorithm besides some linear filtering to reduce noise. A region is displayed by averaging out the colours in that region and assigning a single colour to the entire region. As you can see there isn't much difference between this and the original. Click on the image for a larger view and you should notice the small regions.

This is an example of severe oversegmentation. It was the major problem with the Watershed algorithm when it was first developed. Since then there have been several improvements, one of which you'll see in my subsequent results.


These next two results make use of a very simple smoothing technique to reduce the oversegmentation problem. Gradients form a key role in the algorithm and here I threshold the gradient to reduce the effect of minor differences. The two results below use different threshold values and you should easily be able to spot the differences.

The first is more ideal, with the second being undersegmented. Look at how a large chunk of the hat is grouped together with the background region. Both, however, oversegment the hair and this is where the problem with textures comes in.



There's still a very long way to go here and this is just the beginning of the results. I haven't even tried running with a different image. My eventual goal is to try produce a single segmentation algorithm to cover a wide variety of images. That's where genetic algorithms will come into play to help with the uncertainty of the image.

I must say it's nice to be able to show visual results that probably explain things better than words can explain.

UPDATE: Applying a median filter to the gradient image produces much better results. See the results in the image below. The textured areas are segmented into far fewer regions. The boundary of the hat is fully in tact. The finer details such as the eyes and mouth have less impact on the segmentation. Also, the number of tiny regions resulting from noise is greatly reduced. This shows how how much of an impact such a small change can make.

Computer Science Honours at UCT: Part 2

This is part 2 in my review of the CS honours modules at UCT. Read after reading part 1.

Introduction to Image Processing and Computer Vision (IPCV):

I've always had a small interest in image processing, so I might be a bit biased towards this module. IPCV is lectured by Patrick and I think he does an excellent job of it. He covers topics such as image transformations, feature detection and segmentation. This was also the first of many modules in which genetic algorithms were touched on. It requires a moderate amount of mathematical background, especially linear algebra. If you're into your maths in any way I'd strongly recommend it, but if you're not I'd be cautious, but still consider it. Six of the lectures are used as paper reviews in which you read a paper before the lecture and then discuss it in class.

The assignment is all about using the Hough Transform for circle detection. For those doing the module or any other image-related programming I strongly suggest the CImg library as it has a gentle learning curve and is well documented. The assignment is a simplified version of my second year project and I plenty test data available here.

Parallel Computing (PC):

This is another module I might be a bit biased towards due to personal interest in the subject. I really enjoyed it, even though it was perhaps a little lacking in detail. PC is lectured by Michelle and covers parallel architectures and parallel programming. This year there was a big emphasis on parallel genetic algorithms.

The assignment this year (it changes every year) was to program a parallel genetic algorithm without a library. Parallel programming can be tricky, especially to debug. Added together with genetic algorithms, which can be touchy, made it a not-so trivial task.

I would strongly encourage almost anyone to take PC. It's a nice thing to know how to do parallel programming, especially with the ever increasing number of cores going onto PC processors.

Agents:

I was very excited about taking the Agents module. This was the first time we covered anything related to artificial intelligence and it was lectured by Anet who's research area is agents. It is another one of those modules that has been affected by the introduction of the gaming stream. The Intelligent Systems (IS) module was moved into the gaming stream and we lost the opportunity to take it. So for us, and hopefully the impact will be lessened next year, we had both modules squeezed into one. This resulted in a broad overview of the many AI topics without much depth. Topics covered included neural networks, genetic programming (GP) and several topics related to agents ending off with complex adaptive systems.

The assignment was to program a GP to produce a strategy for predators whose goal it was to capture a single prey. This was one of the more time-consuming assignments, however it was very enjoyable. We had to produce a report on our implementation, which you can read here. The exam is apparently the most difficult of the year and take-home exam. It is often said by ex-honours students and I agree: be scared of open book exams, be very scared of take-home exams!

Genetic Algorithms (GA):

Audrey is one of the newest lecturers in our department and with all senior lecturers required to take an honours module, she started a new one on Genetic Algorithms. I don't want to harp on this too much for her sake, but she wasn't very well prepared and the module ended up having very little content. Most of the lectures were taken by the class, including all the examinable content. Hopefully Audrey will learn from her rough ride this year.

Putting the negatives aside, the module does have a lot of potential. GA's is one of Audrey's main research areas and there's a lot to learn about them. I think some of the GA content covered by other modules needs to be removed in order for this one to become a success. This year we covered the basics of GA's, applications of GA's and GA toolkits.

We each gave a 45 minute lecture in groups of up to three, with each group covering a paper. While it was not for marks, the exam covers a selection of these papers and nothing else. The assignment was to experiment with a genetic algorithm using a GA toolkit and write a report about it. I took advantage of the similarities between this and the Agents assignment and combined them. You can read my report here.

Internet Interoperability (II):

This module is taken by Hussein and that's one of the main reasons I took the module. The other reason is our assignment was all about programming a Facebook application, with the idea being to deal with interoperability issues first hand. I wrote a whole separate post one the assignment here. The module covered several topics around interoperability such as protocols, data/metadata, repositories and web services. It was an interesting module if you're interested in the web at all, but I would give it second thoughts given the choice again.

Intra-Domain Traffic Engineering (ITE):

Of all the modules I took, but not for credit, this was my favourite. Another of our newest lecturers, Antoine, started this as a new module this year. Traffic engineering is all about how to route traffic from source to destination. While this might sound simple at first, just consider what happens when links start failing. There are some fairly complex graph theory problems introduced, such as the K-shortest path problem which tries to get K disjoint shortest paths.

Antoine covers the module at a good pace, allowing for plenty discussion. So many lecturers take their lectures in such a way that almost prevents discussion, which is a real pity when you're in a smallish class. I didn't do the assignments, but there were three of them using NS. The exam is a brief oral exam covering mainly covering the assignments.

Still one more post to come and the module reviews will be done!

Part 3

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.

My Honours Project

For Computer Science honours at UCT we all have to do a big project. The project aims to be the first step towards doing our own research.

I ended up selecting a project on genetic algorithms applied to colour image segmentation. I've since adapted the problem a bit by wanting to study parallel genetic algorithms and more specifically attempting to develop a model that can run on a Grid. My supervisor is Audrey Mbogho and my partner Keri Woods.

Last week I was working on the literature review. It's quite a long and drawn out task to do as you have to hunt down relevant papers. There's plenty literature on image segmentation, to the point where the tricky part was trimming down on the length. There's also a fair amount of literature on parallel genetic algorithms. Grid-based PGAs however - now that's an area that has received very little attention. And the papers I desperately needed I couldn't access. :(

I've just started putting together a page where I've uploaded the documents I've completed so far. Currently it's pretty bare with just my proposal and literature review, although more will be added over time. You can access the page here.