December 02, 2005 —
It’s an annual event: the ACM College Programming Contest.
For 30 years, young computer science students all over the country
|
Cardinal
and Gold: (from left) grad student coach Marcos Vieira, professor David
Kempe, Linda Deng,, Nathaniiel Houk, Cheng-Wei (David) Lin, Josh
Letchford, grad student Marin Kobilarov. Not shown: Professor Sven Koenig, Daniel Birken, Morgan Brown
|
have been testing their skills
against a tough set of problems.
This year, the Viterbi School put
in its best performance in memory, thanks to aggresive recruiting and systematic preparation,
and its Cardinal team came home with a $300 prize from the five-hour
regional (California/Nevada) competition held Nov. 14 in Riverside.
What’s changed? David Kempe, assistant professor of computer
science explained that while the Viterbi School has long had an
excellent
deparment of computer science, in the past, undergraduates wanting to
compete in the annual
competitions have been more or less on their own.
This year, Kempe, his CS faculty colleague Sven Koenig, and
graduate students Marin Kobilarov and Marcos Vieira became deeply involved. First they held on-campus programming
contests to identfy talent, and developed that talent by training two three-person
teams. They drilled the teams in rehearsals of what they could expect.
Kempe underplays the faculty contribution "Our most important role was selecting some
very talented students from a very large pool."
But notwithstanding the talent, a lot of
hard work went into preparation. The teams had no fewer than a dozen
practice sessions, each lasting up to four hours, over the course
of only a month.
The format of the venerable competition
sponsored by the Association for Computing Machinery has long been set.
Teams are presented with a set of problems, each presented on a page.
One used this year was “Grocery Optimization.”
“An enterprising group of Swamp County College business
students have thought of an idea to improve the lives of their
fellow students and perhaps make a few dollars at the same time. They
want to automate comparison-shopping for groceries so students
can stretch their food budgets. A student who wants to use the service
submits a list of commonly purchased groceries along with some
other parameters about their shopping habits, and the service responds
with the store that will give him or her the best deal on those
items that week. The business students hope either to market the
service or to attract sponsors who will support it. The business
students want your team to develop the software that will take each
student’s shopping list and determine which of up to five nearby
stores will provide the lowest net total cost for the selected items.
They will hire other students to collect and enter the data from promotional
advertising and in-store visits. Students vary in the amount of
effort they will put in to stretch their grocery dollars. Some will
clip coupons, others won’t. Some will accept house-brand
substitutes from certain stores, others insist on brand-name goods.
Your program is to take all this into account when determining
which store offers the best deal for each student.”
The teams were given seven similar problems, ranging from concrete
economic questions such as the above, to abstract number theory or game
questions. They had to turn in answers, written in the standard C++
programming
language, with points deducted if an answer was incorrect.
USC’s Cardinal team, made up of Josh Letchford '06, Daniel Birken '07,
and Cheng-Wei (David) Lin '09 solved five of the problems, just one down
from the six solved by the top team, from Caltech.
USC’s Gold team (Linda Deng '06, Morgan Brown '08, and Nathaniel Houk
'08) solved two problems and placed 23rd among the 66 entries. As Koenig
noted, “Considering that none of the USC students had ever
participated in one of these programming competitions before, they
performed fantastically - managing to defeat the traditional
programming contest powerhouses UCLA and UCSD!”
What’s it look like for ’06? Kempe says the outlook is excellent for
next year, when two members of the Cardinal team (including freshman
David Lin) will be returning. The system, he says, works.
"At
USC, we have some exceptional programmers and problem solvers among our
students. Once you've found them and given them a bit
of training, they can battle it out with the best in the world."
Kempe
and Koenig do hope to expand their talent pool beyond CS and even
engineering students — and are trying to put out the word.
"The next contest is coming up in spring, and we want lots of people to participate.
