Programming Contest Prep


mini contest

Fall 2007 Contest

This site will host materials for preparing for the upcoming regional programming contest on November 3, 2007.  Each week I will add new problems for you to work on.

Meetings

You may work on the problems on your own. Or you may find it more fun to come to meetings and solve problems with other students. Due to scheduling conflicts, I propose two meeting times:
You're welcome to show up at both meeting times. I will show up on Wednesdays after my evening class around 9pm, and on Fridays at 3pm. We can discuss the problems and your solutions at those times.

The problems

General
  1. Palindromes (posted 9/13/2007)
  2. Find the telephone (posted 9/13/2007)
  3. Jolly jumpers (posted(9/21/2007)
  4. Can of beans (posted(9/21/2007)
  5. Stacks of flapjacks (posted 10/5/2007)
  6. Maximum sum II (posted 10/5/2007)
Data structures
  1. Simply subsets (posted(9/21/2007)
  2. Hoax or what (posted(9/21/2007)
  3. The window property (posted 10/5/2007)
  4. Climbing trees (posted 10/5/2007)
Recursion
  1. Fractal (posted(9/21/2007)
  2. Number of paths (posted(9/21/2007)
Sorting
  1. Exact sum (posted 9/13/2007)
  2. Lunch in Grid City (posted 9/13/2007)
  3. Shoemaker's problem (posted 10/5/2007)
  4. DNA sorting (posted 10/5/2007)
Dynamic Programming
  1. Let me count the ways (posted 9/13/2007)
  2. String computer (posted 9/13/2007)
  3. History grading (posted(9/21/2007)
  4. Fast food (posted(9/21/2007)
Backtracking
  1. Addition chains (posted(9/21/2007)
  2. Graph coloring (posted 9/21/2007)
  3. Anagram checker (posted 10/5/2007)
  4. Blackbeard the pirate (posted 10/5/2007)
Searc
Graph Theory
  1. Thunder mountain (posted 9/13/2007)
  2. Internet bandwidth (posted 9/13/2007)
Number Theory
  1. Twin primes (posted 9/13/2007)
  2. Euclid problem (posted 9/13/2007)
Geometry
  1. Circle through three points (posted 10/5/2007)
  2. Cops and robbers (posted 10/5/2007)

Resources you will need

Steven S. Skiena, Miguel A. Revilla, Programming Challenges, Springer, 2003. ISBN: 0-387-00163-8
An Algorithms textbook
A Data Structures textbook
A reference book for the programming language you will use (C, C++ or JAva)

Online References

Here are relevant web sites:

ACM-ICPC website
Mid-Central USA Programming Contest website
Programming Challenges textbook web site
ACM-ICPC Live Archive (includes automated judge)
UVa problem set archive and online judge (the above problems come from here)
Article on how to prepare for the contest
Standard Template Library Programmer's Guide
C++ reference