A team of students from the University of Waterloo have triumphed in a five-hour battle of logic and skill, placing first in a global computer programming contest.
Months of practice doing similar types of problems was a big part of the strategy behind winning the ACM International Collegiate Programming Contest, said David Kennedy, first year masters student in computer science at the University of Waterloo in Waterloo, Ont..
“Part of the challenge is really looking at a question and knowing how to do it very quickly. [Working with a team,] you get a feel for what each other’s strengths are, as far as different types of problems.”
Nearly 6,000 students representing 59 countries competed in regional preliminary contests last fall. The top 10 teams went on to compete in the World Finals, which were sponsored by IBM Corp. and held this year in Eindhoven, Netherlands. The Waterloo team consisted of Kennedy, Ondrej Lhotak, Viet-Trung Luu and reserve member Donny Cheung.
The student teams collaborated to write programs in C, C++, Java and Pascal to solve eight real-world problems in a span of five hours – and there was only one computer allotted to each three-person team.
Kennedy said this aspect was particularly challenging. “I mean sure, it’s coding ability and how well you can program, but a lot of it’s teamwork, and how well you can share that single resource of the one keyboard and one monitor,” he said.
“If someone is working on something and you decide you can do something else quicker, you just have to step in and kick them off the terminal.”
According to Kennedy, that scenario occurred quite often at the World Finals.
“At one time all three of us were working on different problems. One of us was trying to code up the solutions and the other two were trying to work out bugs. And it was just a matter of rotating to the terminal to make sure we got all of our goals done without stepping on each other’s toes too much,” he said.
“You have to check your ego at the door, because you are working with two other very strong programmers who deserve to be there just as much as you do. And so does everyone else around you.”
Sometimes this meant scribbling solutions down on a notepad while waiting for a turn, Kennedy said.
“A couple of the problems involved three-dimensional mathematics. And sitting down and working those things out on a paper before getting anywhere near the terminal was an absolute must, because if you don’t have the math figured out beforehand, you can’t really go anywhere with the problem.”
During the contest, every time a team solved a problem they got a balloon, with a colour representing a specific problem. Many of the first balloons raised were the same two or three colours, as the international teams determined which were the easiest problems and worked on them first.
“It’s kind of a good feeling to know you are ahead – it gives you encouragement to work a little harder. But in the last hour, everything gets thrown out the window – you have no information at all,” Kennedy said.
“But when [the announcers] got up to number two, and it wasn’t us, we knew then that we had won.”
The computer problems were presented by ACM and IBM staff members, said Gabby Silberman, program director at IBM Corp.’s Centre for Advanced Studies in Toronto.
“It’s not just dreaming up the problems, but coming up with the solutions so the judges can [determine what’s correct]. It takes a bit of work to get that right, because most of the judging is automatic. The problems are set on a scale where most teams will solve at least one, and most teams will never solve all of them.”
According to Silberman, the contest grew 50 per cent in participation from 1998 to 1999. This was the first time Java was used in the contest, as well as the first year Japan and Africa have competed. Each member of the first and second place teams received an IBM ThinkPad, while third place winners received an IBM WorkPad. All the top 10 teams won ACM scholarships as well.
Gordon Cormack, team coach and computer science professor at Waterloo, said the contest gave the students an opportunity to use a variety of different programming skills and algorithms.
” We cover an awful lot of material, algorithms and programming. Often [the students] find they learn very large amounts of computer science in the course of a few months that otherwise they would learn in a trickle. We end up touching on a lot of core material that would be third- and fourth-year graduate course material.”
Teamwork and strategy were also crucial, he said. “They really have to trust each other. I’ve seen teams break down, especially when they are getting incorrect judging or something like that. And if they start second-guessing one another, then they’ve lost.”