SciTech

Carnegie Mellon students to compete in programming world finals

Credit: Maria Raffaele/Art Staff Credit: Maria Raffaele/Art Staff Teams of three students are given eight to 10 problems to solve in a five-hour limit. Pictured above is an example problem that was used in the 2008/2009 ACM ICPC World Finals in Stockholm, Sweden. (credit: Example problem adapted from Association for Computing Machinery) Teams of three students are given eight to 10 problems to solve in a five-hour limit. Pictured above is an example problem that was used in the 2008/2009 ACM ICPC World Finals in Stockholm, Sweden. (credit: Example problem adapted from Association for Computing Machinery)

This May, a team of three Carnegie Mellon students will participate in the world finals of the IBM-sponsored Association for Computing Machinery (ACM) International Collegiate Programming Contest (ICPC), also known as the Battle of Brains. These students are among around 300 out of 97,000 students to advance all the way to world finals, 0.3 percent of the original pool of contestants.

The contest began over 30 years ago, held at Texas A&M and hosted by the Alpha Chapter of the UPE Computer Science Honor Society, starting out as a much lower-scale contest than what it is today. Doug Heintzman, IBM sponsorship executive for the ACM ICPC, explained that the contest was a friendly, relatively low-key competition between mostly North American schools for the first 20 years or so. “Then it kind of blew up into what it is today, with some 2,000 different schools from about 90 countries.... It has morphed from being the experimental thing 20 years ago to being this global, international, very large-scale phenomenon,” he said.

The rules and procedures of the contest are as follows: Every participating team consists of three students, and they are given between eight and 10 problems to complete in five hours or less. Each team is only allowed one computer to work on, which is provided by the organizers of the contest.

Tom Conerly, a senior computer science major and member of the Carnegie Mellon team participating in the upcoming world finals, explained that people would normally check how well their code is working by running it, but because each team only has one computer, a different strategy is taken. “One person’s typing on one half of the screen, and on the other half of the screen another person is staring at the code trying to figure out why it’s not working,” Conerly explained.

The questions that the teams must solve range in difficulty, and involve coming up with a solution that will work over a range of scenarios. For example, a problem may ask for the minimum amount of fencing needed to enclose a certain number of trees. But the teams may not know the position of the trees or how many of them there are. The judging uses various “test cases,” which are different combinations of tree numbers and positions, to test how universal a team’s solution to the problem is.

Once the problems are submitted for judging, they are judged as either “correct” or “incorrect”; the solution either works for all test cases, or it does not. There is no partial credit. There is also a time penalty if teams submit a solution after the five-hour limit. The team that solves the most problems in the fewest number of attempts in the least amount of total time is deemed the winner.

Conerly will be competing in the world finals with fellow student-teammates Nate Barshay and Si Young Oh, all of whom are also majoring in computer science. This year, the world finals are being held in Orlando, Fla. at the Peabody Orlando Hotel and Conference Center. Originally, Cairo, Egypt was slated as the host city, but due to Egypt’s recent uprising and social unrest, the world finals were moved to Orlando.

The coach of the Carnegie Mellon team, Danny Sleator, a professor in the computer science department, helps organize practices that take up at least 10 hours a week.

“This is like quiz bowl, except I think this is somewhat more substantial, because you really have to do something more creative and with more depth to it than answering a question about some vice president in the 1800s or something,” Sleator said. “Sometimes you have to create a new way of doing something. You have to invent new ideas that you’ve never heard of before.”

Though IBM does use the contest as one source of recruiting (the top-12 finishers receive a full-time job offer), Heintzman reflected on the more altruistic reasons the contest is held. “There are lots of really big problems [in the world] that are going to require some really clever problem solvers that know how to not only use but develop the state-of-the-art information,” he explained.

“We think it’s very important to shine a very bright light ... and tell the story of how remarkable these young people are, and the responsibilities that are going to be sitting on their shoulders as they enter the workforce and start participating and solving some of these big challenges.”