Programming team takes byte out of competition
Three teams of University of Chicago students tested their mettle last year against a “deranged algorithms professor” in a regional contest of computer programmers.
As a final exam, the hypothetical professor “throws his students into a maze formed entirely of linear and circular paths, with line segment endpoints and object intersections forming the junctions of the maze.” And it was up to the contestants to figure out what that meant, and program a computer to rescue the poor, hypothetical students.
Not a single team in the region managed to solve the problem. But one of the University’s competitive computer programming teams, called “Works in Theory,” performed especially well at the International Collegiate Programming Contest (ICPC) regionals. Vying with 7,000 teams from more than 1,800 universities in 88 countries, the team has advanced to ICPC’s World Finals.
Now the Chicago undergraduates will travel to Stockholm, where the top 100 teams worldwide will compete for the world championship April 21.
Works in Theory
Works in Theory consists of Ian Andrews, second-year in Computer Science; Lauren Ellsworth, third year in Law, Letters & Society and Computer Science; and Louis Wasserman, a first-year planning to major in Mathematics. Their coaches are Borja Sotomayor, doctoral candidate in Computer Science, and Michael O’Donnell, Professor in Computer Science.
Organized by the Association of Computing Machinery, the annual contest starts with a regional phase, which runs from October until December. During these five-hour contests, students write programs in C, C++, or Java to solve eight problems on a computer.
“It is rare for a team to solve all eight,” Sotomayor says. Contestants are not allowed to see the scoreboard during the final half-hour, which makes for especially tense finishes.
“The regional judges typically take classic computer science problems, but state them in a non-obvious and generally playful way,” Sotomayor says. One classic problem involves finding the shortest path around a maze. This was the infamous “deranged algorithms professor” problem.
The scoring scheme rewards the number of problems solved and speed, but getting a problem wrong results in a penalty. “There is a lot of strategy involved,” Sotomayor says, because students must decide which problems to solve first, and whether to risk submitting a possibly incomplete solution.
After a team correctly solves a problem, it receives a colored balloon that corresponds to the problem. “After a few hours, you end up with a computer lab filled with balloons,” Sotomayor says.
Judges’ Cave
Coaches also serve as contest judges. They work out of a separate room—the Judges’ Cave—and score the results through an online grading system.
“We have to grade problems right away,” Sotomayor says. Although aided by a grading system, they sometimes debate the verdicts and respond to student requests for clarifications. “Occasionally, we’ll even find a flaw in one of the problems and will have to re-judge problems on the fly.”
The Computer Science Department has sent teams annually to the Mid-Central USA regional contest for nearly a decade, and previously qualified for the World Finals in 2001 and 2002. This year the department assembled three teams.
The teams placed first, second and ninth at the Chicago site (University of Illinois at Chicago). They placed third, fourth and 21st in the Mid-Central USA region, which includes more than 150 teams in Arkansas, Illinois, Kentucky, Missouri, and Tennessee.
By Steve Koppes
