Logo: University of Southern California

Student Programmers Shine in ACM Competition

Stars Will Return in '06; Recruiting Continues

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.
More details are available on the project website, http://www.cs.usc.edu/contest/