At some point in elementary, high school or university, everyone has faced text-based mathematics problems that seem deceptively simple, but actually require a lot of thought to work through.
You're given facts and numbers in a story format, and you have to arrive at an accurate conclusion based on the information as presented. While some people breeze through the problems, others are completely, utterly stumped.
If you've ever stared at a page of these problems and wondered – "Who thinks these things up?" – you only have to look to Dr. Howard Cheng (mathematics and computer science) for the answer.
Cheng has been creating, and helping students solve, these simple but deviously complex problems for the past eight years as a volunteer, coach and lead faculty member of the U of L teams that compete in the Association for Computing Machinery (ACM) International Collegiate Programming Contest (ICPC).
His work, combined with the students' dedication and interest, is paying off.
Four, three-person teams of students recently competed in the ACM/ICPC regional programming contest, which involved universities and colleges across North America. The teams are made up of primarily undergraduate and masters-level students who cross disciplines in mathematics, computer science and physics.
The U of L group placed third overall in the competition, and two U of L teams finished in the top half of the 51-team roster. While an excellent result, it regrettably left them out of the running for the international competition, which takes place in May 2012 in Warsaw, Poland.
"I learn a lot from this experience as well," says Cheng. "The students did a great job this year and I am proud of them."
Cheng and the team train for the competition for months beforehand. Beginning next term, a specifically designed course (CPSC3200) will begin – created to make the most of the ACM/ICPC format as a hands-on educational experience for the students.
Cheng knows well the stress that the contest places on the students. He competed in 1997 and 1998 while a student at the University of Alberta, and made it to the world finals. He has created problems for regional and international competitions, and continues to be involved in the ACM/ICPC organization as a judge and mentor to other teams.
So, what does it take to be able to solve a typical ACM/ICPC contest question? Cheng has selected some problems from the recent competition for the Legend's readers. Try these yourself and see how you do. As with the student challenge, you have about an hour.
1. EMPTY THE PILL BOTTLE: Each day, you wish to take half a pill from a bottle. If you happen to take a whole pill, you take half of the pill and put the remaining half back in the bottle. How many ways can you empty a bottle with 30 whole pills initially?
2. APPLY FOR CITIZENSHIP: You are given the dates of your immigration application, start of residence, landing date, as well as the date of all your trips outside of Canada. When can you apply for Canadian citizenship (using official rules)?
Cheng has posted the complete problem statements on his website (www.cs.uleth.ca/~cheng/contest/probs.html)
You are welcome to send your answers to Cheng at howard.cheng@uleth.ca to see how you've done. A winner, if there is one, will be announced in a future edition of UWeekly.
This story first appeared in the December 2011 issue of the Legend. If you'd like to see the full issue in a flipbook format, follow this link.