CS98-1/CS198-1 Assignment #3

Due: Thursday., 18 Sept. 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 as follows:

• Create a subdirectory of your instructional account called ~/cs198-1, and in it create a subdirectory ~/cs198-1/3.
• Place sets of input data in files called test-P.N in directory ~/cs198-1/3, where P is the problem number, and N is a sequence number: 0, 1, 2. 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.
• Protect your directory with the command

     chmod -R a+rX,go-w ~/cs198-1/3
  

• If your home directory is not currently world-readable, protect it with

     chmod go=x ~
  

  which makes it possible to get to readable files in your home directory if one knows their name, but not to list the files in your home directory.

Problems

1. 1995 Berkeley Programming Contest, Problem 3 (Clunk).
2. 1996 ACM Programming Contest Finals, Problem C (Cutting Corners).
3. 1992 Berkeley Programming Contest, Problem 6 (Snark and Borogove).

[Course Home Page]