Student Programmers Shine Even More Brightly in 2006 ACM Competition

Eric Mankin
November 17, 2006 — It wasn't a fluke! USC Viterbi School CS students followed up their outstanding performance in last year's ACM Collegiate Programming Contest with an even more impressive one in this year's competition.

Number 2 in the region:  (l-r)  Morgan Brown, Kenny Daniel, Daniel Birken (all photos by Li Zhang)

For 30 years, young computer science students all over the country have been testing their skills in this grueling contest against a tough set of problems. In the 2006-7 Southern California Regional held on Nov. 11 at Riverside Community College, all three USCteams turned in strong performances — and one, the USC Trojan team, made up of Morgan Brown '08, doctoral candidate Kenny Daniel, and Dan Birken '07, scored second out of 70 teams from all over the region, behind only a team from Caltech.

The USC Cardinal team, (Cheng-Wei David Lin '09, Michael Rodgers '07 and Denis Tulskiy '10) was thirteenth and narrowly missed beating the best UCLA team. Team USC Gold (doctoral candidate Thang Dinh, Noel Overkamp '10, Prateek Tandon '10) placed 26th. The USC on-site reserve was MS student Bo Yuan.

"These are fantastic results on the part of the students, even topping last year's 5th and 22nd places of our two teams, " said CS assistant professor David Kempe, who with fellow CS faculty member Sven Koenig and PhD students Marin Kobilarov, Marcos Vieira, and Li Zhang coached the three teams.

The format of the venerable all-day competition sponsored by the Association for Computing Machinery has long been set. Teams are presented with a set of problems, each on a separate page.

Team Cardinal: Denis Tulskiy, Cheng-Wei David Lin, Michael Rodgers

One used this year was "Bad Birthday Present."

On my birthday my cousin Larry gave me a box inside a box inside a box inside a box inside a box, and there wasn’t anything inside the innermost box! Now his birthday is coming up. Of course I’m not so crass or unimaginative as to do the same thing to him, but if I were, how many boxes could I force him to open? Your team is to write a program that will help me calculate that.

To do that, you’ll be given several lists of boxes. For each list, your program’s job will be to compute the greatest number of boxes in that list that can be nested. More specifically, you’re to compute the size of the largest subset of the boxes in a list, such that the smallest box of the subset fits within the second smallest, the second smallest of the subset fits within the third smallest, the third smallest fits within the fourth smallest, and so forth….

The teams were given seven such problems. They had to turn in answers, written in the standard Java or C++ programming language. They gained points for speed; they lost points for false starts and computer runs that didn't correctly solve the problem.

The USC Trojans team solved five of the seven problems in a total time of 11 hours and 20 minutes, with only three bad runs. The winning Caltech A team solved six of the seven in 11 hours 26 minutes, with five unsuccessful tries.  USC Cardinal solved four with three bad runs in 14:09; USC Gold finished three, with three bad runs in 10:13 

Team Gold: Thang Dinh, Noel Overkamp, Prateek Tandon

Kempe had many benefactors to thank. "The Viterbi School and the Computer Science Department both offered money and support," he said.  Industry also pitched in: Kempe and the team are all grateful to Electronic Arts, Symantec and LanguageWeaver for their help.

The team members for the Regional Contest were selected mostly from successful participants of the USC Programming Contest, which is held once a semester, and open to all interested undergraduate students, regardless of their major.

The fall on-campus competition took place Saturday, September 9, and attracted a record 49 participants who competed for cash prizes totaling $1000 contributed by the sponsors. Of those, 37 students solved at least one problem, 29 solved at least two problems, and 15 students at least three problems. The top performer, Daniel Birken, solved five problems to win the $400 first prize.

The next USC contest will be held this spring and Kempe encourages computer-savvy students — "no matter what their major" he emphasized — to consider entering. Further information is available at http://www-rcf.usc.edu/~dkempe/contest

What’s it look like for ’07? " We are looking forward to doing even better next year, of course," said Kempe.

"We are enormously proud of our teams," said CS chair Gérard Medioni, "and congratulate them all, and their coaches, on their remarkable success."

Click on the logo for general ACM information. Specifics on the Southern California regional are here.