So a bunch of gophers are located in front of a bunch of gopher holes. Only one gopher is allowed in each hole. The gophers have exactly T number of seconds to reach the hole before they get eaten by a hawk, and you can spare a certain number of gophers. What’s the least amount of time needed to save all the gophers that need to be saved?
You may have no idea, but junior Ben Mickle does.
“Well, first you run a binary search on the farthest distance the gopher needs to go to get to the hole,” he said. “Then, for each distance, you run a maximum bipartite matching problem. If you can match out a sufficient number of gophers, you try to decrease the binary search. If you can’t match up enough, you increase the distance on the binary search.”
It might sound like gibberish, but for a group of Duke students, those words may be the key to a world championship win.
In addition to Mickle, freshman Matt Edwards and senior Garrett Casto form Team Magabe, a Duke computer programming team led by Coach Owen Astrachan, professor of the practice of computer science.
The team qualified to participate in the world’s most prestigious computer competition—the World Finals of the Association for Computing Machinery International Collegiate Programming Contest, sponsored by IBM. The competition, in Shanghai, China, began April 3 and will run through April 7. In order to qualify for the competition, which brings together the top 78 teams from around the world, Team Magabe beat out more than 100 teams to place first in the Mid-Atlantic regional.
The grueling national competition is five hours long, and each team of three students has one computer to solve eight to 10 complex problems equal to a semester’s worth of computer programming. Some of the questions involve several hundred lines of code. To get points, the submitted programs must be completely free of bugs, and the team that takes the least amount of time to finish the most programs wins. Recent winners have included teams from Poland, Russia and China. A U.S. team has not won since 1997.
As a requirement to participate in the regional competition, the three students took Astrachan’s course, Computer Science 149S. But each had also had previous programming experience. In high school, Casto and Edwards became involved with TopCoder, an online league for programming competitions. Mickle started programming in eighth grade, creating games on his TI-83 calculator.
“We always have teams that could do well; we just never know if they are going to,” Astrachan said. “The team this year is three good programmers—we don’t have a team of all Americans, but we have a team of good guys that practice well together.”
Casto, Mickle and Edwards believe the key to their success as a team so far has been a result of their various individual strengths. Casto does well with computational geometry, Mickle said, so they tend to give him those problems. Mickle said he prefers the “number theory stuff” and Edwards does better at “figuring out weird things... to implement stuff.”
The team said they will have to overcome the jet lag caused by the 13-hour time difference in order to avoid making careless mistakes—one error in a program as trivial as a missed semi-colon could cost hours of time.
“Sometimes it’s hard to focus for five hours. In the World Finals the problems are so different your brain starts to give up eventually,” said Casto, the only member of the team who has gone as far as nationals before.
“I’m looking forward to it. I guess I’m a little nervous,” Mickle said. “I wouldn’t say there is too much pressure though.”
Still, the team is an underdog. “We’re West Virginia in the NCAA tourney,” Edwards added.
Once the competition starts, the team is on its own. According to tournament regulations, coaches can watch from the stands, but guards are stationed nearby to make sure they do not try and interact with the students.
Although Astrachan is a coach, he said he has a different role than most coaches have in sports. “Any role I have is before I go,” he said. “The only thing I can do there is to make sure they get plenty of sleep.”
The contest can also be something of a recruitment mechanism. Students in the contest often go on to internships with IBM during the summer and the school year.
“Many of them are very accomplished and high potential individuals. When they are ready to take on a job, we hope they will give us full consideration so we try to keep tabs on them,” said Gabby Silberman, program director for IBM Centers for Advanced Studies and sponsorship executive.
The winners will get to take home what the Association for Computing Machinery and IBM have dubbed the “World’s Smartest” trophy, a combined $10,000 of scholarship money and loads of IBM goodies like IBM Thinkpad laptops.
Get The Chronicle straight to your inbox
Signup for our weekly newsletter. Cancel at any time.