Computer Science Dinner

Last night was the annual Queens’ Computer Science dinner and we completely sold out of tickets for the second year in a row.

Ben and Matt did an excellent job as this year’s organisers – everything ran smoothly, and they had even arranged for some live music as we moved from the main dining hall to Old Hall after dinner (for more food).

I’d like to thank the individual alumni who sponsored the dinner and also the corporate sponsors: Palantir, Jane Street, Ocado, Coherent Graphics, and Encore.  Your generous support is what makes the dinner possible.

We were lucky this year to have Siraj Khaliq as our guest of honour.  Siraj studied Computer Science at Queens’ in 1997.  He was one of the first 300 employees at Google and then went on to do his own startup The Climate Company which was acquired by Monsanto for $1.1 billion.   Siraj gave a great talk about his experiences and had advice for those of us thinking about startups today.

One of his pieces of advice was to not try to build the ‘best’ thing when ‘good enough’ is good enough.  I think this is worth remembering – I can think of numerous occasions in research where we’ve had an idea, let it get shot down by some corner case and then seen papers from people who’ve done the same thing, not worried about these cases, but still found something interesting.

I was really pleased to see so many graduates who came back and joined us. It was interesting to hear how everyone is getting on.

Here’s a shot of a few of us at the drinks reception:

Drinks reception in the Old Senior Combination Room

Drinks reception in the Old Senior Combination Room

And here’s a picture of me with Professor Alan Mycroft and Dr Anil Madhavapeddy. Alan and Anil were chosen by the Queens’ undergrads as their favourite lecturers this year.

IMG_20150517_224022

Thanks everyone for coming, thanks to Ben and Matt for their hard work organising, see you all next year.

Probabilisitic datastructures

Advait (our AI supervisor) gave a good talk last week on probabilistic datastructures. He showed how you could save orders of magnitude of space if you were prepared to have an almost right answer (with probability bounds).

He motivated the talk using the example of MildyInnappropriateCatAppreciationSociety.com which is trying to store unique pictures of cats. You can use a bloom filter to do the same job as a hash table here.   If you had 40Mb of raw cat pictures then you could use a 0.6Mb bloom filter an an efficient way of looking up whether you already had a certain picture with 4% error. If you wanted an exact answer with (e.g.) a hash table it would take you 4Mb. Obviously in reality you would have petabytes of cat pictures – then the savings start to add up.

We then looked at cardinality estimation – this is the problem of estimating how many unique cat pictures we have.  For our 40Mb example above you can do this in 125kb using a linear counter, or in 2kb using a loglog counter.

The next question was counting the frequency of each cat picture.

One might say we are trying to graph the long tail of cats.

One might say we are trying to graph the long tail of cats.

A count-min sketch can do this in just 48kb of space (with 4% error).

We went in to each of the above in detail to understand how they worked and Advait had a quiz on each one to see how they would store some example data.

Advait is using probabilistic algorithms in his research on visualising large datasets and so to close he showed us a sneak preview of his upcoming publication on this.

The talk was presented really clearly and confidently with lots of audience interaction.  All the talk of cat databases gave us a real world (!) scenario for the algorithms.  And it was nice to hear a bit about his research too.

Robot battle

On Wednesday last week we played Robocode.

For those of you who’ve not seen it before its basically a simulator for battles between robot tanks.  You play the game by writing Java code to control your tank and try to destroy everyone else.

We had three teams, each of which was tasked with writing two robots.  Then, after 2 hours, we had a tournament to see which robot was best.

Here’s a video of Sid2 fighting Larry.  Sid2 (you can guess who wrote that) was built by copying and pasting example code off the web (this turned out to be a very good strategy for building a good robot in 2 hours).  Larry was a more customised effort featuring a colour changing technique (for no particular benefit in battle):

After beating Sid2 we thought Larry was going to emerge the winner but then ProbablyTerribleRobot came on the scene:

Here’s a video of all of our robots in melee.  Special mention to Robotina and FirstRobot for their very novel movement patterns…

Educational Lego

Last night we practised Agile software engineering using Lego.   Stephen (who supervises Object Oriented Programming) is a certified Scrum Master and so led a session explaining the Scrum process.  We then put it into practice doing short 5 minute sprints building a Lego themepark.

Phase 1 was to build the project backlog.  We did this with postit notes stuck to the wall.  There were some logistical issues about getting everyone near enough to see though.

IMG_20150429_185740

Here’s a picture of one team mid-sprint

IMG_20150429_190347

Here’s (some parts) of the finished theme park.  Note the self-driving car with ‘built-in’ RFID tag.

IMG_20150429_202609

And here’s my favourite model: its a travelling salesman who is holding the solution to the P=NP problem:

IMG_20150430_140514

First meeting of term

We’re  back.  Yesterday was the first meeting of term.  We had updates from third year students about how their projects are getting on.  And 7 of this term’s supervisors came to join us.  Due to popular demand I’m going to be supervising Mobile and Sensor Systems this term for the third years.  A major topic of my research over the last five years has been mobile phones and energy consumption so hopefully that will help.

After the meeting it was dinner as usual and Eduard told me how he spent his time over the vacation solving the First round of Code Jam using only Excel.

Second year group project demos

Last Wednesday was the culmination of the second year group projects.  We had an afternoon of demos followed by lightning talks from each group showing off their projects.

Here is a brief summary of the projects that the Queens’ students worked on:

Retail Category Manager:  Tatsiana’s group were given the brief of making it easier for retailers to list their products in online marketplaces like Amazon.  The idea was to auto-categorise a list of products based on keywords in the name and description.  They adopted a neat Bayesian approach which they trained on the products already categorised in the marketplace.  This had a nice effect that if a misclassification occurs it can be manually corrected and then the prior probabilities can be updated to reflect the new knowledge.

Location Based Teaching: Radu and Sid’s project was to build a location tracking system which tracked smart phones using iBeacons.  They then implemented a location-based callback system so that you could be notified of interesting events near-by in the building.  The location system worked by matching fingerprints of visible beacons with a previously created fingerprint map.  They managed to get quite accurate results (within 10 metres) in some parts of the building.  However, in more open spaces the accuracy was less good (sometimes even putting you on the wrong floor).   They built an Android app and a website which worked pretty well.

Sid demonstrating his location-aware Android application to Ramsey.

Sid demonstrating his location-aware Android application to Ramsey.

Building the Matrix:  Katie, Ben and Jamie got to play with two Oculus Rift headsets.  They had to build a distributed multiplayer virtual reality game. A lot of work went into this since they built their whole 3D engine from scratch in C++.  The game was bumper cars.  They had managed to get the latency on the headtracking down really well so when you moved your head the view updated very smoothly.  However, the latency of the game controls was quite a bit bigger – that’s my excuse for why I kept getting bumped off the track.

Ben and Jamie demonstrating their virtual reality game.

Ben and Jamie demonstrating their virtual reality game.

Micro friends video diary: Matt’s project involved automatically summarising video.  Their software automatically generates a short 3 second highlight clip of your video and shares in on a social network that they built.  They used various image processing algorithms (such as face tracking) to try and work out which were the best frames to include.  And they built an entire social networking website for people to share and follow other peoples video clips.

Well done to everyone for successfully delivering your projects on time.

A Friendly Competition

This week, in a session run by Jan, we were split into teams comprising one student from each of the first, second and third years and presented with a series of increasingly difficult problems to solve. There were fantastic prizes such as chocolates, flapjacks and even bottled water available for the winners, the runners up and, well, pretty much everyone.

Three people enter a room, each one with either a blue or a red hat on their head. They do not know the colour of their own hat but they can see the hats of the other two people. Once they had a chance to observe the colour of the other hats, they can guess what colour their hat is or say nothing. All guesses happen simultaneously and no other communication is allowed. if no one guesses wrong and at least one person guesses correctly, they win, otherwise they lose. Given that the colour of each hat is assigned randomly by a flip of a fair coin, what is the best strategy and how often does it win?

The first question was one of probability. Surprisingly unintuitive, perhaps you wouldn’t expect there to be a strategy any better than picking at random, but you’d have to think again. Radu, on my team, got to the answer fairly quickly but it took much longer for him to convince Holly and me that he was correct!

You are given two hourglasses. One measures 4 minutes and the others measures 7. Can you measure 9 minutes?

Bonus: given two hourglasses that measure n and m minutes, what values of k minutes can you measure and how much set up time do you need?

This question is closely related to the perhaps more widely known problem of measuring a specific amount of water given two unmarked jugs that are known to hold n and m litres respectively. You can fill the jugs up, empty them, or transfer water from one jug to the other until one is either full or empty. You can’t, say, pour out half of the water, however: you have no way of measuring exactly half, just as you have no way of knowing when exactly half of the time from one of the hourglasses is up in this problem.

Our team solved the hourglasses question more quickly than the first one, perhaps because all of us had seen the isomorphic water jugs question before.

Given a standard 52 card deck, 5 cards are randomly chosen by a member of the audience and given to a magician. He then selects one of the cards and keeps it, while arranging the remaining four cards on a table face up. A second magician then determines what card the first magician kept. What strategy did they use?

Note that while arranging the cards on the table, only their order can be significant, e.g. you cannot rotate them in any way to give extra information to the second magician.

In this clever question, it appears at first as if you do not have enough bits of information available to communicate which of the remaining 48 cards has been selected. Indeed, our team almost didn’t believe that was possible at first, and not one of the teams present was able to solve the problem after almost twenty minutes of discussion.

Eventually, Jan stepped up to the whiteboard and explained the solution — after a few people left the room, determined to come up with an answer themselves and refusing to have the game given away to them. Even once it had been explained, many of us didn’t see how the solution worked until we had discussed it amongst ourselves for another five minutes!

Following this question, the hour for the meeting was almost over, and besides, the non-muggles among us had to leave to go to a Harry Potter themed formal hall. But the dedicated computer scientists stayed for one final enigma.

You are given 3 Turing Machines and want to determine which ones terminate and which ones don’t. You have access to an Oracle that, given a Turing Machine, tells you whether it terminates or not. However you can only query it twice.

Again, this question seems impossible because you are only given two bits of information and must seemingly use those to distinguish between 8 different possibilities. However, a solid understanding of the theory of computation led Eduard to a brilliant way of generating that final bit that the Oracles cannot themselves provide.