Programming Assignment 1

Assigned: Jan. 19.
Due: Feb. 9.

Assignment

Write a program that solves the Post correspondence problem, as described in Problem Set 1, using the following algorithm:

Input

Your code should accept the following inputs: You may set default values for B, C, and D above, or you may require the user always to set them explicitly. They must be settable at run-time; there will be a deduction of 4 points out of 10 for any program that hard codes these or the dominos. However, your code may include a maximum allowable value for B, since that corresponds to a memory limitation.

Output

The program should always output one of the following three: In addition if the flag in (D) above is set, the program should output the sequence of states generated in searching for the solution.

Coding

Programs will be accepted in C, Java, or Scheme. If you wish to write programs in other languages, you should discuss that with the TA; I leave that decision entirely up to his/her discretion. Programs must run on the department Sun system; you should check this before you submit your code.

Submit

The source code and a README file explaining how to compile and run your code.

Grading

Grading: 8 points for correctly running code. 2 points for well-written code. A programming assignment count equally with a problem set in computing the overall grade.

Late policy

Programming assignments due at the beginning of class on the due date. I will accept assignments late with a penalty of 1 point out of 10 for each week late (fractions of a week are rounded up.)