Ondřej Lhoták is an Associate Professor at the Cheriton School of Computer Science. He has a bachelor’s degree in mathematics from Waterloo, and an MSc and PhD in computer science from McGill. He joined the Cheriton School of Computer Science as faculty in 2006. For his significant contributions to program analysis and aspect-oriented programming, he received the 2013 Outstanding Young Computer Science Researcher Award from CS-Can | Info-Can, the non-profit professional society that represents computer scientists and the interests of their discipline across the nation.
But to computer science students and alumni, Professor Lhoták is probably best known because of his involvement with the International Collegiate Programming Contest, first as a participant while an undergrad at Waterloo and now as a coach.
Waterloo is the only Canadian university to have won this prestigious international programming competition, first when Ian Goldberg (also a professor at the Cheriton School of Computer Science) and his team mates Seiji Ando and Ka-Ping Yee won the 1994 ICPC world championship. Then, several years later, Professor Lhoták and his team mates, Viet-Trung Luu and David Kennedy, won the 1999 ICPC world championship, coached by Professor Gordon Cormack.
Professor Lhoták explains what the ICPC is, how it evolved, and Waterloo’s participation and victories at the ICPC.
What is the International Collegiate Programming Contest?
The ICPC is an annual multi-tiered competitive programming contest. The ICPC has a long tradition dating to the 1970s. It started as a small, local programming competition in the United States, but it grew to be a US-wide contest and eventually one that included Canada. Since the 1990s, the ICPC has been an international university-level competition with teams from countries across the world.
What is an algorithmic programming competition?
The thing that makes the ICPC unique is the tradition of having challenging algorithmic problems that have attracted top students across the world for decades.
At the contest, each team of three individuals is given problems to solve, usually between eight and twelve problems. For example, you have a map with cities and roads and distances and your task is to find the shortest distance between two cities. The problem statement won’t give you a specific map, it will just tell you what the map will look like. The solution involves finding an algorithm — a procedure — that if you follow blindly will give you a solution to that problem. The solution has to be general, so no matter what the specific problem instance is, no matter what map you get, no matter what the distances are, if you follow the steps you’re guaranteed to get the correct answer. So, the first step is to find the algorithm or to invent an algorithm to solve the problem.
The second step is to implement that algorithm in a programming language so a computer can run it. These two steps are interesting because some students are great on the algorithmic side and others are great at writing code. To do well at the ICPC, the team has to have both skills and it requires teammates to work quickly, efficiently and collaboratively.
The judges run the code on a set of problem instances to test that it correctly solves all of them. If the solution doesn’t work the judges say so, but they won’t tell you what you did wrong. It’s up to the team to figure out where the problem is and how to fix it. Teams have five hours to solve eight to twelve problems with algorithms that are correct and with code that’s correct.
How does the multi-tiered competition work?
For North America, the contest has two rounds, a regional round, which in our case has teams from universities in Ontario and teams from universities in the surrounding states in east central North America competing to determine which one is the regional winner.
The top few teams from each region go on to compete at the ICPC world finals. There, you typically have a hundred teams from around the world. But only one team from any given university can compete at the finals. That’s been unfortunate in Waterloo’s case because sometimes our teams have come in first, second, third and fourth in the regional competitions.
How important is collaboration in solving the problems?
A team needs abstract thinkers to come up with algorithms and it needs quick coders to test the algorithmic solutions on a computer. And if it doesn't work, to find the error in the algorithm or the code and fix it.
The contest is designed to require collaboration. You have a team of three, but only one computer. The one computer rule really forces the need for cooperation. One person can be typing away writing the code, but the other two members of the team need to help and find ways to be useful. The team has to work collaboratively to solve the problems, but also to find mistakes and correct them — and all within the five hours of the contest.
Did you compete in other math and computing contests?
Nowadays, there are a number of contests leading up to the ICPC, many high school contests including the Canadian Computing Competition and the Canadian Computing Olympiad run by Waterloo and CEMC.
A big deal for me as a high school student was becoming involved in the math contests that the CEMC runs. They were a big eye-opener and made me aware of Waterloo and had a huge influence on me. In my final year of high school, I participated in the Canadian Computing Competition, during the first year it was held. It’s a programming contest similar to the ICPC but at the high school level. That’s when I started participating in programming contests in addition to math contests.
The Canadian Computing Competition was my first programming contest and that’s where I found out about the ICPC. Ian Goldberg, who was a few years ahead of me and was on the winning team in 1994, gave a talk about the ICPC. It was then that I became interested in more than just math contests.
How did it feel to be the winning team at ICPC in 1999?
It was surprising, both in the moment and over the long term. The contest is five hours long, but in the last hour the judges stop the scoreboard. As a team you know if you’ve solved a problem, but you don’t know what problems other teams have solved.
We knew how many problems we had solved, but another six or seven teams were likely close enough that they could have won. Afterwards, there’s an awards ceremony where the results are announced. It wasn’t until the second-place team was announced that we deduced we were first. It was suspenseful right until that very moment.
The ICPC world finals is a huge event that’s held in a different city every year. A hundred or more teams of three participate, so aside from the contest itself it’s a place where you meet a lot of bright, motivated people. Just going to the finals is a prize, being part of that group.
You and Troy Vasiga have coached Waterloo’s teams for several years now. How do you prepare teams to succeed at the ICPC?
The number one aspect for success is to attend a good school — be at Waterloo. We have outstanding talent coming in every year. A huge part of our successes at the ICPC comes from the outstanding students we have. And one of the reasons we attract outstanding students is that they participate in this long tradition of math and programming contests we run. Many people at Waterloo have been offering and running math and computing contests, and over many years they’ve helped attract the best students.
At our local ICPC-like contests we create the problems, organize and run the contests to determine which participants will form the regional teams. Some years we get students with a lot of experience — maybe those in their third or fourth year — but we also get a lot of first-year students. The trick is to balance the raw talent you might see in first-year students with those that have more experience.
What do students learn and gain?
The ICPC is a contest with a long tradition and a big reputation. There’s the social aspect of the ICPC, working with other students who are exceptional. I participated in the ICPC for the fun of solving the problems, but a big part is meeting all the other teams. You learn a lot from the other people at the contest. It’s exciting to be part of that and it opens doors for participants, whether to grad school or employment.
Students also learn a lot, things like abstract problem-solving skills, the ability to invent algorithms, and the ability to code them up quickly. In a sense, it’s a form of prototyping, quickly prototyping correct, running and working code. It motivates students to balance theory with practice. They also quickly see that they don’t just learn from textbooks and professors. They learn from each other, and this peer-to-peer learning is very important.
Flashback to the 1999 ICPC World Champions in Eindhoven, The Netherlands
From a field of more than 1,900 teams in intercollegiate competitions worldwide, 62 teams of students advanced to the 1999 World Finals of the ICPC held at Eindhoven University of Technology, The Netherlands. Prizes, scholarships, and bragging rights were at stake for some of the finest students from universities and colleges worldwide.
That year, the ICPC world championship went to a team of programmers from the University of Waterloo — Viet-Trung Luu, David Kennedy and Ondřej Lhoták, coached by Professor Gordon Cormack.
L to R: Viet-Trung Luu (holding the winning cup), David Kennedy and Ondřej Lhoták
L to R: Gordon Cormack (coach), David Kennedy, Viet-Trung Luu and Ondřej Lhoták
