Programs, poker & Stockholm

A team of Oxford computer scientists recently won a silver medal at the ICPC event in Stockholm where contestants from around the world battled it out to solve tough programming challenges against the clock.

I quizzed the team about what they did, what they learned and how computer science could improve your poker skills... 

OxSciBlog: Why do you think competitions, such as the ICPC, are important for computer scientists?
Frantisek Simancik: Programming competitions are here mainly to attract new students to computer science.  I myself learned my first programming language only because I wanted to take part in a local contest at my secondary school.

They give us a chance to compare our abilities with others and motivate us to learn more and to be better. You know what it's like: give your students homework and they will look at it on the day before the deadline, set the same problems as a competition and they will strive to be the first to solve them. And they will even want more!

OSB: What was the most challenging problem you managed to solve?
FS: The difficulty of problems varies widely from ones you can solve immediately after reading to those on which you can spend hours on in vain. Often there are even problems which don't get solved by anyone at all.

The most difficult problem we solved this year was probably "videopoker" from the regional round of the ICPC. The goal of the problem was to write an optimal poker player whose actions would always maximise its expected winnings. While this may sound as a fairly standard task, we were the only team who managed to make their program work in time.

Daniel Bundala: One of the most challenging problems we solved is the following: A botanist has a plant initially consisting of a single cell of a given type. For each type, you are given the sequence of cells the cell of that type divides into. For example, a cell of type A may divide into the cells of types BABC, cell of type B into CC and so on.

The plant evolves in stages and every cell divides according to the rules at the beginning of each stage. The task is to determine whether this cell structure converges to a stable state. This problem is from a regional round and it is one of the practice problems we solved before the world finals. 

OSB: What did you learn from the competition that you will apply to your studies at Oxford?
Daniel Bundala: Programming competitions have helped me a lot in developing my problem solving skills. Although the problems concentrate mostly on algorithms, which form very important but quite small part of modern computer science, I have noticed that solving this type of problems improved my skills in solving problems in completely different areas as well. And as the exams are approaching, it is quite handy to be able to solve difficult problems quickly.

Also, ICPC is a team competition and I have learnt that it is very beneficial to have someone to discuss the problems with. Very often, we were presented with a problem I would barely solve on my own, but working on it with the teammates, we managed to solve it reasonably quickly.

OSB: What area of computer science are you most passionate about? Why?
Jakub Zavodny: It was programming competitions that introduced me to computer science, so originally I was most interested into algorithms, complexity theory and discrete mathematics. Although I mostly stayed on the theoretical side of computer science and in mathematics (in fact all three of us study the Maths & Computing joint course), I enjoyed many new areas to which the university lecture courses exposed me. I will be starting a PhD with the Quantum Computer Science group here at Oxford this fall. 

Jakub, Daniel and Frantisek are based at the Oxford University Computing Laboratory.