Carnegie Mellon Dragons Take On the World in International Programming Competition

Freshman Evan Danaher and sophomores Thomas Quisel and Glenn Willen are headed to China but they don't speak Chinese. Lucky for them, the only language they need to understand on their trip to Shanghai April 2-7 is the international language of computer programming.

The three computer science students, known collectively as the Carnegie Mellon Dragons team, will go head-to-head with more than 200 of the world's "best and brightest" programmers at the IBM-sponsored Association for Computing Machinery (ACM) International Collegiate Programming Contest World Finals April 3-7, in Shanghai, China. The Dragons will take on 77 other teams from around the world in their bid to bring the trophy and the bragging rights that go with it back to the United States for the first time since 1997.

Begun in 1970 at Texas A&M University, the International Collegiate Programming Contest (ICDC) has expanded into a global competition headquartered at Baylor University that involves tens of thousands of students and faculty from universities in 75 countries. Organizers call this "battle of the brains" the oldest, largest and most prestigious programming contest in the world.

More than 4,000 teams representing 1,582 universities began the quest for the World Finals in different regional competitions across the globe this past fall. The Carnegie Mellon Dragons earned a berth to the World Finals, which will be held at Shanghai Jiao Tong University, by placing in the top three schools at a competition at Carnegie Mellon in November.

"This is the world's premier university competition in the computing sciences and engineering," said Bill Poucher, ICPC executive director and Baylor professor. "IBM, ACM and the world's universities have partnered to offer the best and brightest students the opportunity to challenge themselves to achieve far beyond classroom expectations so that they can build the cutting-edge technology of tomorrow."

Designed to foster creativity, teamwork and innovation in building new software programs, the contest challenges teams to solve a series of complex, real-world problems—equal to a semester's worth of computer programming curriculum—on one computer in just five hours. Under the eye of the expert competition judges, the teams rank the difficulty of the problem, determine the requirements, design test beds and build software systems that solve the problem This programming, though, is nothing like homework problems.

"There are really three subproblems you have to solve for each problem in the contest," said Willen. "First, taking the description and figuring out what they're asking you for mathematically—what real problem they want you to solve. Once you know that, you have to come up with a mathematical or computer algorithm to solve it. The third part is to actually write a program that implements it correctly. With any luck, it works the first time and doesn't have bugs."

Time is also of the essence. "There's a lot more time pressure," said Danaher "And there's also the issue of having three people on one computer. So if you have a program that's not working do you debug it at the computer or do you print it out and do it by hand, and let someone else type another program in? The time management gets to be a problem."

Students do not have a copy of the judges' test data and acceptance criteria, and the team receives a time penalty for any incorrect solutions. In the end, the team that solves the most problems in the least time wins. Wrong answers, then, can spell disaster for a team.

"The really great teams can get it right the first time," said Willen. "They will get maybe one problem wrong and have to resubmit once or twice in the whole contest. Maybe not even that."

To place themselves among those great teams, the Dragons have held weekly practice sessions all semester. They began as three-hour practices as part of lecturer and co-coach Greg Kesden's class, Competition Programming, and have progressed to five-hour sessions, using problem sets from past World Finals.

With all this practice, the Dragons still doubt their ability to bring home the first-place trophy. "Kesden's been saying top 25," Danaher said.

"I think he's being unnecessarily optimistic," Willen said, while Quisel noted "lower is to be expected."

Despite his team's doubts, Kensden thinks they'll surprise everyone—including themselves.

"They are an absolutely outstanding team; they will do very, very well," said Kesden. "Some other teams might get ahead of them, but only from more experience. Our team is very young. ... A couple more years and they will be unstoppable."

For more in the ACM International Collegiate Programming Contest, visit http://icpc.baylor.edu/icpc/

Though the Dragons didn't bring home the ACM International Collegiate Programming Contest World Finals trophy, the team did receive an honorable mention for their performance. The spoils went to Shanghai Jiao Tong University, which also hosted the event. The "Battle of the Brains" will start up again in the fall, when regional competitions begin across the globe.

Susan Cribbs
April 1, 2005