Keep Talking and Nobody Explodes

This week’s Wednesday meeting saw the Queens’ CompScis participate in a somewhat different activity: bomb defusal.

In Keep Talking and Nobody Explodes, a player is locked in a room with a bomb that will imminently go off, and has five minutes (or less) to defuse the bomb by disarming several complicated modules. However, they have absolutely no idea how to defuse the bomb. Thankfully, the other players are equipped with a bomb defusal manual — but they can’t see the bomb, so everyone involved has to communicate quickly and clearly to stand a chance of survival.

keep_talking_and_nobody_explodes_meeting

Having arranged ourselves into threes and deciding on team names, we got to work. The game proved to be quite interesting, and certainly tested our ability to convey information accurately and under pressure. We deciphered confusing symbols, disambiguated between lots of homophones, and tried to tackle a light displaying Morse Code, although around half of us found it impossible to coherently read out the rapid sequence of dots and dashes.

Overall, we enjoyed improving our communications skills in a fast-paced and competitive game environment. Congratulations to Dhruv, Henry, and Tamara, who managed to defuse 9 bombs by the end of the session! Also thanks to the developers of Keep Talking and Nobody Explodes for providing us with copies of the game.

Game Theory – NIM and Sprague-Grundy

Last Wednesday we were given a talk by Radu, one of the third year students at Queens’. His talk introduced us to some interesting and cool concepts in game theory – a topic that relates well to Computer Science, such as in problems where the optimal play must be taken.

Radu’s talk focused on NIM-style games. The aim of the game is to be the last player to be able to play a move. The image below shows an example – three piles of coins exist, and a each turn a play is allowed to take as many coins as they like, from a single pile (they must take at least one coin). IE, the player could take all the coins from pile one, and then it would be the opposing players turn.

Screenshot from 2016-01-26 12-09-24

Through the clever use of XORing the numbers, Radu went on to show that calculating and making the optimal play is very easy. Once a player has forced themselves into a winning state (where the XOR-Sum of all numbers is 0), as long as the player maintains the optimal play, they cannot lose.

Screenshot from 2016-01-26 12-16-34

Moving on from the NIM game, Radu went on to show (Via the Sprague-Grundy theorem) that many games can be reduced into a NIM game, and thus an optimal solution can be found. One such example is represented in the image above, the “Poison Chocolate Problem”, where a player can take any row(s) or column(s) in a single turn, but must not be the player to eat the poisoned block.

Interview preparation

Its interviewing season again. We start on Monday. If you are reading this and you are coming to interview at Queens’ this year then please try not to worry too much. Our goal in interviews is to find the best in you and not to catch you out. Just be yourself.

We have a new test which you’ll be taking on the interview day this year called the CSAT. There’s lots of information about it online (including a practice test): http://www.cl.cam.ac.uk/admissions/undergraduate/admissions-test/ One thing to bear in mind when doing the test is that its supposed to be challenging: don’t worry if you can only get a few done.

Jake and I did a video a while ago about what the interviews will be like. Its still relevant. In fact the new first years this year said they were surprised when they came to interview about how realistic it is!

The art of the Elevator Pitch

How well could you pitch something in the time it takes to get to the bottom floor?

This week Ramsey taught us the facts about first impressions: the first is that when you walk into a room you have 7 seconds to make an impression and the second that you then have just 100 seconds to keep the audience involved. This is a technique used not just in pitches but also in interviews where the main aim it to pitch yourself.

There are 3 key components to an elevated pitch: the hook, a power of 3 and the wrap-up.

The hook is your 7 seconds to truly impress whether that be with a stat, fact or bold statement. The more extreme the numbers the better.

The power of 3 is a psychological  tool used by both Martin Luther King and Tony Blair. It allows you to provide 3 key facts about the topic – it also apparently works very well for online dating.

The wrap up is the concluding statement of the pitch and should be altered to fit the purpose. It may be a call to action giving you the chance to demonstrate a project; a link back to the hook if you have finished your presentation or else a leading question can be used to engage the audience into further discussion. This, we were reliably informed by Ramsey, can also be used to put competitors on the spot.

During the presentation we learnt about the empowering body language we should employ. The most empowering is standing with your hands up in the air , like a gorilla, but this is ill advised in public places. Before presentations the wonder woman pose should be used to exert that display of confidence over the room as demonstrated by Ramsey.

One a aspect of body language many think is irrelevant but which is actually one of the most important are the hand gestures. Hands should either be steepled – like Tony Blair – or fisted like many politicians. We should never point as it reminds people of being told off or count on our fingertips as it is reminder of when we were children.

Before we got to attempt our own elevator pitches Ramsey pitched NAVSOP to us demonstrating all the techniques we should you use.

Splitting into 4 groups we all attempted to pitch very different things to the group. Henry Aspegren pitched “The jellyfish case” because who hasn’t dropped their phone. Rob pitched Andy reminding us how useful he is for lack of procrastination. Dhruv shared with us his dislike for the Cambridge Gown whilst Henry Thompson pitched… what was it again?? Oh yes Refresh.

I Thought I’m Studying Computer Science. Why All the Maths?

Last year my friend from another UK university has told me his algorithms exam question which went along the lines of this:

Your friend from Cambridge has implemented a binary search tree. Unfortunately, due to lack of practical skills, he has made some mistakes. Help him fix it.

I found it hilarious solely because there’s a grain of truth in every joke – Computer Science degree in Cambridge is indeed pretty theoretical, with courses like Logic and Proof, Computation Theory, Complexity Theory, Semantics widespread. At some point in your degree you feel like yelling into the abyss about why are you suffering through all this stuff.

That’s where Sid comes in with his talk this week. Breaking the holy tradition of speaking about his Part II project, he spoke about the mathematical history of the foundations of Computer Science instead to convince us all that these theoretical courses are all in fact integrated in the core foundation of CS.

It all began with Russell’s Paradox of a set of all sets that don’t contain themselves. This resulted in Russell’s and Whitehead’s conclusion that the Maths is broken. To be fair, they didn’t simply break Maths and ran away giggling, but instead tried to fix it in a book called Principia Mathematica by introducing some really simple axioms and some rules which we apply to prove things. And all was good with the world until Gödel broke it again.

sid_slide1

Sid’s translation of Gödel’s theorems to English

That made David Hilbert come up with Entscheidungsproblem (judging from the name, I guess he was angry at the time) – given a logical statement with a bunch of axioms deciding whether it’s valid. Then Alan Turing came along and thought that we can find if something is valid with what we currently think of as an algorithm. He then built an imaginary machine, Turing machine, that solved this problem and discovered that a general solution to this problem is impossible. In the meantime, Alonso Church approached this problem with lambda calculus and came to the same conclusion.

They later collaborated and came up with Church-Turing Thesis, stating that a function on the natural numbers is computable if and only if it is computable by a Turing machine, where computable means that one can compute it in his head. Furthermore, everything that can be computed mathematically can be computed by lambda calculus, while everything that can be computed by lambda calculus can be computed by a Turing machine. Great! Now we have defined our goal to make a system be able to compute computable things – we want a system to be Turing complete.

But what do we actually need to create a Turing complete system? Sid then shows that 6 things: constant function, successor, projection, function composition, primitive recursion and minimization are enough. Not satisfied, he then shows that actually 3 things are enough with SKI combinators. Not satisfied, he then shows that actually 2 things are enough since we can express one combinator through other two. Still not satisfied, he then shows that actually 1 thing is enough and introduces us to iota combinator. Since no one in the audience would’ve believed that 0 things are enough, Sid finally gets satisfied and stops.

sid_slide3

UUUUUUUUUUUUUUUUUUUU

But all of this history comes with some powerful takeaways. Computer Science essentially came about from a bunch of people thinking very hard about what it was possible for the brain, Maths or a machine to do. So in essence, Computer Science is not about programming. It’s about proving theorems, which programming is basically like. Sure, one can abstract himself from such an analogy and never go below the code level, but being exposed to theoretical foundations of CS can be proven valuable to understand the nature of this subject and as such Sid’s closing message was for everyone to try and take the most out of these courses now that they are aware of why Cambridge is teaching them.

In my opinion, it was a great talk and I really enjoyed this packed history lesson. But the most memorable part of the evening was Sid’s delivery packed with jokes at every corner including bashing PHP, using a grumpy cat, legitimately proving that P = NP, showing an XKCD comic on fetishes, deriving Andy’s banterousness, asking the audience a question where all answers were wrong, repeatedly breaking Maths, referencing popular songs by Hozier, Daft Punk and Mark Ronson, using the word “bae” and pretending that people won’t ask him questions if he asks for it.

sid_slide2

Disclaimer: the author of this post does not claim knowledge of the post’s topic. All contents are interpreted from Sid’s talk. If something in this post is wrong, blame Sid.

Object Tracking for Image Annotations

This week we had Matt present his Part II project to the group.

A big part of machine learning research at the moment has been creating and training algorithms to recognise objects. To feed these algorithms training data, traditionally you have had to go out and take thousands of pictures of your desired objects, say a human, and then ‘annotate’ the image, letting the trainer know where in the picture the human actually is. As you can imagine, annotating all of these images is a long and very tedious task that is difficult to automate. This is where Matt’s project comes in.

His idea is to take a video of the target object in various positions, say a human walking down a road, instead of separate photographs. What Matt’s project would then do is track the object through the video automatically, finding it’s position in each frame. This position data then gives the training set hundreds of annotated photos, each a frame of the video that it can then use to train.

To teach everyone about how an algorithm may go about tracking an object, Matt first took us through some of the basic techniques currently used, such as finding the gradients of an image by applying different kernels. For example, the image below shows the calculated gradients of an image, which can be seen to be a face. These gradients then give us a higher level look at the image, which is much better to work with then just raw pixel data.

face

However there are better methods that can be used, such as cross correlation, the method Matt is using in his project. Here, the algorithm gives us a ‘mask’ that we can apply to an image, and this mask will produce a sharp, centred white spot if the applied image matches the object, and a faded white image if not. This is an accurate algorithm, but is extremely expensive to use, as it has an O(p*p) complexity, where p is the pixel count. To improve this time complexity, Matt then showed us a mathematical method you can use to find the result of the cross correlation algorithm much quicker using the Fourier transform. We then had a demo where Matt showed the result of his work on this algorithm, which successfully recognised a face in various positions.

How did we spend the summer?

It’s that time of year again where the Part IBs tell us all how productive and useful their summers were. And, indeed, what a wide variety of entertaining and interesting activities were undertaken! Brad now has a 10% equity share in a new start-up, Sam ate a lot of donuts, Alex devoured dominos, Henry milked the stock market, and Rob developed racing game mods!

Sam kicked us off, telling us about the free beer at the pub with his colleagues and his work at RealVNC. He was using Java and C++ at the Java Native Interface level, writing software to bring VNC into customers’ cars. RealVNC is a commercial product used to remotely access and control a desktop or mobile. It’s a based on an Open Source core component to which RealVNC add features geared towards enterprise or typical home users. After his intense work and dedicated donut eating, Sam flew off for a much needed holiday.

The world is full of surprises and opportunities and Brad’s exemplifies this! He ended up working for a person Tatsiana (an MIT exchange student at Queens’ last year) met on a plane whilst she was jetting around Europe last Christmas. Brad was tasked with building the back-end analytics of the start-ups app, coded using Scala and Apache Spark. Additionally, he delved into tedious and frustrating administration work with the Amazon EC2 servers. Brad’s view on Amazon EC2 is short and simple, “Would not recommend!” As if all that wasn’t enough, he managed two separate teams in India where they had outsourced the iOS and API development of their product. A thoroughly enjoyable experience, despite having to sack one of the teams… Ah well, all’s well that ends well and it certainly did for Brad as he flew out with the family to the gorgeous Caribbean for a nice relaxing break.

Henry was luxuriating in his longest summer ever, June through to October, thanks to the early ending of MIT semesters and the late start of Cambridge terms. Aiming to maximise his summer productivity, he got himself hired by Goldman Sachs, working in their New York offices which he emphasises is an amazing place to be. It’s all very hush hush but, what he could divulge was that he worked on the algorithms used for trading stocks. In Henry’s words, “it’s like playing poker…except instead of James Bond it’s a computer program … and its trading one million dollars’ worth of US Equities faster than you can blink.” Let’s let that sink in for a moment…

Alex spend his summer in a very exotic place: the William Gates building! Otherwise known as the Computer Lab, which is where lectures take place for IB and II students. Alex worked on the Pyland project with a team of fellow first year students, working to add a slick user interface and error message diagnostics on top of the engine build by last year’s Pyland team (including yours truly). Furthermore, he delivered a whirlwind of presentations to a diverse spectrum of audiences, including teachers and Raspberry Pi enthusiasts.
Rob spent his summer rewriting (sorry, I mean improving) Matt’s app for the Naked Scientist. The original app was written just for Android but Rob made use of Xamarin, a cross platform development platform using C#, to build both an Android and iOS version. He ported Matt’s code to C#, added in the needed glue code and then worked on enhancements including some cool server-side Python scripting (Rob now likes Python).

The evening was wrapped up with the unanimous and entirely voluntary election of Sid to the role of President of the Queens’ Computer Science Society. We wish him all the best as he takes on his role this year!

Note: It should be recorded that in the awards ceremony for the best talk, Eduard (Queens’ resident Part III student) decided to award himself third place and one donut for his colourful and all-encompassing summer holiday presentation slide. This was Eduard’s backup slide in case any Part IB missed Eduard’s rigorously enforced submission deadline…summer blog