• Departments & Offices
• Reves Center
• International News & Announcements
• 2012

All about the algorithms

Competitive programming team prepares for World Finals

Sometimes the guys on Team Gold say “worlds.” Other times, they say “finals.”

Both terms refer to the World Finals of the Association for Computing Machinery’s International Collegiate Programming Contest (ACM-ICPC) to be held in May in Warsaw, Poland. Team Gold is going—and they’re going to compete against the top young computer programmers on earth.

Team Gold is Michael Christensen M.S. ’12, Brett Cooley ’13 and Aaron Dufour ’12. The three earned a berth representing William & Mary at the finals after a stellar showing in early November at the Mid-Atlantic Regionals, placing second among 166 teams. (William & Mary also had another squad at regionals, Team Green.) Ever since, Team Gold has been in training for Warsaw, where they will compete against 110 teams of the world’s top student programmers.

This is the first time a William & Mary team has advanced so far, says Debbie Noonan, an instructor in William & Mary’s Department of Computer Science. Noonan has coached the College’s competitive programming teams for the past 15 years and she’ll be accompanying Team Gold to Warsaw, along with her husband, Bob Noonan, a professor in the computer science department.

Coach Noonan says that the scenario at worlds will be similar to the regional competition. Only one computer and keyboard is provided for each three-person team. The teams are given a list of eight problems to solve and the clock starts ticking. The team who solves the most problems correctly in the allotted time wins.

 “A large part of the competition is figuring out what to work on first and who should work on it,” Christensen said.”

Divide and write code

To solve the problems, the team applies algorithms, the step-by-step instructions that are the basic vocabulary of human-computer communication. In competition, two members of the team typically work on paper while the third is at the keyboard, so that the team is working on at least two problems at any one time, Noonan said. Some competitors try using the most fleet-fingered on the team as a designated typist, but Team Gold has developed its own answer to who gets the keyboard.

“It’s generally useful, regardless of typing speed and other considerations, to have the person who thought out the problem and came up with the algorithm to type it up,” Cooley said. “A lot of times we’ll write a lot of code on paper, since there’s only one computer. But you don’t necessarily write it out line for line.”

When the team believes it’s solved a problem, the solution is sent out for review by judges. Incorrect solutions are returned with comments that might have been taken from the world’s worst Turing test: “incorrect output,” “bad output format” or maybe “running time exceeded.” Teams get a penalty for each bad solution sent for judging, Noonan said.

No one uses words like “underdog,” but there’s a sense that William & Mary is punching a bit above its weight at the World Finals. Many of the teams that Team Gold defeated in the Mid-Atlantic Regional were from schools with mammoth computer science departments that sent as many as nine teams to regionals. Christensen just came back from a round of job interviews (he’s accepted a position at Microsoft, by the way) in which his berth at the World Finals generated a gratifying amount of interest. He learned that several big schools have for-credit courses taking dead aim at getting a team to the World Finals.

William & Mary doesn’t have those sorts of resources to dedicate to getting a team to worlds, but as Cooley says, “The CS department has given us what we need to succeed and do well.” Noonan explains that the basis for success is the department’s Analysis of Algorithms course.

“Many problems will fall into a particular category of algorithm, and if you apply the right algorithm to the problem, that works,” she said. “Hopefully, the guys can apply strategies to the competition problems based upon what they’ve learned in Analysis of Algorithms.”

Banking on diversity

Team Gold is taking to Warsaw the same feature that caused them to be a giant-killer in regionals. Christensen sums it up in a single word: diversity.

“Aaron is a physics major and math minor. That was really helpful at the regionals because there was something in there about the speed of light and he knew how to reduce the formula intuitively, which was amazing,” Christensen explained. He added that Dufour also has been programming the longest of the three, but Dufour notes that the competition will be using Java.

 “It’s a language that I’m not terribly familiar with,” he said. “And I’m probably the slowest typist.”

Cooley points out that Christensen, as a graduate student, adds to the diversity of the team: “He’s already got a bachelor’s degree. He’s taken courses that Aaron and I haven’t.”

The members are aware that diversity has another side.

“We definitely have put less preparation into working as a team for regionals than most of the other groups,” Dufour said. “We probably have some catching up to do on that.”

Training sessions once a week

To hone their teamwork skills, the three meet for practice sessions every week. They began by discussing a practice problem that each has been working on individually. As worlds gets closer, they’ll move into more real-time drills that simulate competition conditions.

The computing industry takes a keen interest in the members of the teams who advance to the World Finals; such a competition is a wonderful way to identify the best and the brightest among the crop of new computer programmers. Corporate sponsorship is allowing the University of Chicago to invite all the North American teams going to worlds to participate in a practice competition. Team Gold is going of course; it’s all expenses paid.

The logistics of getting to Warsaw posed a number of challenges as well. To make connections and get to the competition on time, Team Gold will have to leave the U.S. on May 13. That’s the day of William & Mary’s commencement and Dufour and Christensen are receiving degrees. There was some anxiety that they might have to miss the big day, but Noonan worked it out.

 “You know, their parents spent a lot of money to get them through school and they want to see them graduate,” she said. “It turns out there are some flights out of Richmond that were later in the evening. Now they can actually go to commencement and get their picture taken with their parents and still get to the World Finals.”