CS98-1/CS198-1 Assignment #6

Due: Thursday, 9 Oct 2003 at noon.

Read the attached three contest problems carefully. After doing so, decide with your partner on which of them you will do; both partners should produce their own versions of each problem. Make an estimate for each of how long it would take you to write a working program to solve them. The constraints on your solution are that you want to write a program quickly that is good enough to produce results for the expected sorts of input in, say, 15-30 seconds.

In conjunction with each problem, develop a set of test data and a set of results. Your partner and you should test each other's program on each other's test data. Please check this page from time to time for further instructions on turning in your test data.

Select at least two of the problems and develop solutions (in Java, C/C++, or Python), keeping track (be honest!) of how long it takes you. Compare these times with your estimates. What took more (or less) time than you expected, and why?

Hand in your solutions electronically. Here's how. Hand in your test data using the following new procedure:

• Place sets of input data in files called test-P.N, where P is the problem number, and N is a sequence number: 0, 1, 2, etc. So test-1.0 is the first (zeroth) set of test data for problem 1.
• Place corresponding files containing expected results in files called result-P.N.
• Make sure you have a compiled version of your solution (named P, as created by contest-gcc) in the same directory as those tests (the test-submission program will insist that your program pass all your own tests)
• Hand in your tests for problem P by using the command

     submit-tests P
  

  in the directory containing the tests and the compiled version of your program. This will find all test files in the current directory with appropriate names and mail them to me.

Problems

1. 1993 ACM Programming Contest Finals, Problem H (Scanner).
2. 2001 Berkeley Programming Contest, Problem 1 (Counting Paths).
3. 1998 ACM Programming Contest Finals, Problem F (Polygon Intersection)

[Course Home Page]