Programming Assignment 1

Assigned: Jan. 25.
Due: Feb. 22.

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. Use a simple format for inputting, but do not hard code any aspect of the input.

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, C++, Java, Scheme, Perl, or Python. 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 the format of your input and 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.)

Sample Inputs

Format:
First line: max size of queue (item B)
Second line: Max total number of states (item C)
Remaining lines: Dominos

Input 1
Input 2
Input 3
Input 4
Input 5