Programming Assignment 1
Assigned: Jan. 25.
Due: Feb. 22.
Write a program that solves the Post correspondence
problem, as described in Problem Set 1,
using the following algorithm:
- In the first stage of search,
use a breadth-first search through the state space of Problem set 1,
problem 4 until the queue of frontier states has reached a specified
maximum. (You should, however, build the lists backward as in problem 3;
it's easier and more space efficient to
build linked lists backward than forward.)
Use a hash table over strings to eliminate repeated states.
- In the second stage of search, use iterative deepening starting
from the frontier created in the first stage, until a specified limit
has been reached.
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.
- A. The set of dominos.
- B. The maximum size of the queue used in the breadth-first search.
- C. The value of some kind of parameter
(e.g. maximum depth; maximum number of states;
maximum run time) that will to prevent the program from
going into an infinite loop. Note that the program can go into an
infinite loop either in stage 2 or in stage 1, if the search
can proceed without exhausting the queue, so the limit must apply to
- D. A flag indicating the type of output, as described below.
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.
- A sequence of dominos that solve the problem.
- A flag indicating that no solution exists.
- A flag indicating that no solution was found within the limits of search.
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.
The source code and a README file explaining the format of your input and
how to compile and run your code.
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.)
First line: max size of queue (item B)
Second line: Max total number of states (item C)
Remaining lines: Dominos