Computer programming team places first in regional competition

The UW–Madison computer programming team “Red No. 40” beat 198 other teams to place first in the North Central Regional Competition of the International Collegiate Programming Competition in early November, qualifying the team to compete in the World Finals in April.

Red No. 40’s members consist of UW–Madison juniors Jason Malinowski and Chunsong Wang, and first-year graduate student David Malec.

The computer programming competition serves as a magnet for job and internship recruiting for technology companies such as Microsoft, Google and its sponsor, IBM, all of which consider its participants among the brightest young computer scientists currently in school.

“From a completely selfish standpoint … it gives us direct access to a very focused, highly skilled talent pool that we aggressively hire from,” says Doug Heintzman, IBM’s sponsorship executive of the ICPC.

The competition is based on three-member teams tackling real-word problems with algorithms, or lists of specific instructions for solving the problem, then coding them into computer science languages such as C++ and Java that allow the solution to be tested on computers. The word problems encompass a wide variety of topics, tackling anything from figuring out the most favorable schedule for a team in a soccer tournament to the most efficient way of cutting power lines between cities as part of a military strategy.

The diversity of the problem sets reflects the even larger diversity found in how algorithms are used in the real world, with everything from Google’s search function to the human genome project making use of the rule lists.

“We’re also very aware that information technology and computer science, for a whole bunch of reasons, whether it’s understanding the human genome project and doing weather modeling or providing infrastructure for the response to disasters, is an absolutely key, critical component of solving some of the world’s biggest problems,” Heintzman adds.

This will be a UW–Madison team’s eighth trip to the World Finals in as many years. UW–Madison began regularly competing in the ICPC in 2001 when current coach and UW–Madison computer science professor Dieter van Melkebeek began working with interested students.

Van Melkebeek says the size of the competition and the problems programmers face make it unique for competing students. The ICPC is run by the Association for Computing Machinery, which is the largest professional organization for computer programmers. It is one of the oldest computer competitions, dating to 1977, and it has been sponsored by IBM since 1997.

“The problems are typically quite wordy compared to when we give problems in programming classes, which are very well specified — you need to do this. Here, often part of the problem is extracting what you need to do,” van Melkebeek says.

Another key factor in the competition is time: If an algorithm takes too long to complete its run with the judge’s test data, it gets sent back to the students with an error message. Whether it’s for taking too much time or a coding error, teams are penalized 20 extra minutes for each wrong answer submitted, which can hurt the team in the frequent event of a tie-breaker.

The competition is judged first on the number correct of the eight to 10 problems in a set, then on the number of minutes used to complete the problems.

“What is often called the naive approach is that [a particular algorithm] will work, but it might take some time to run,” says team member Malinowski. “For example, if I give you a bunch of cities on a map and I ask you what’s the shortest path to visit every city exactly once? One thing you could do is look for every single possible path and do it, and then figure out which one is the shortest. That’ll work, but that will take a long time to run, and so you hope to find more efficient ways of doing those things.”

The competition’s combination of extensive problem-solving, devising an algorithm and coding it often means different divisions of labor for each team.

“This year, the team was ordered where one person was very good at coding, one person was very good at algorithms and then one person was very good at both, so they strategized based on that,” van Melkebeek says. “One person comes up with the algorithms, then discusses with the other ones, tells them what exactly needs to happen, then another person codes that up.”

Malinowski says the team plans to separate work in this manner more often in the World Finals, which test on much more difficult problems that will likely require more reliance on each team member’s strengths.

The highest a UW–Madison team has placed in the World Finals is 11th. As the competition has expanded under IBM, teams from eastern Europe and China have dominated the competition at the world level, van Melkebeek says.

“For these schools, one of the highest honors they can get is to represent their team on this competition and do really well,” he says. “Some of these guys are almost professional programming competition participants. They work from one competition to the other and just skip classes … Sometimes here it’s a bit of challenge to really convince the really good students to participate because it’s a significant time commitment.”

Wang, who came to UW–Madison this semester from China, has competed for his home country in the competition in the past, has also noticed differences in each country’s competitors.

“I think students in China who participate in this competition do it because there are some benefits to students to get from the competition. … In America, the students are in this competition mainly on their interests, I think,” he says. “In China, we practice more, but I can’t tell whether it is good.”

Malinowski agrees with Wang, adding that while the ICPC competition is a resume-booster for jobs, it’s also entertaining.

“It’s partly an extracurricular, it’s partly just for fun and the spirit of competition,” he says. “That’s probably the number one reason to do it — it’s just fun.”