Programming Assignment 1
Assigned: Jan. 18.
Due: Feb. 8.
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 2 until the queue of frontier states has reached a specified
maximum. (It's easier to build linked lists backward rather than
Use a hash table over strings to eliminate repeated states.
That is, if the same strings on top and on bottom can be generated by
more than one sequence of dominos, only one of these need be kept.
- 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.
- 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, 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.
The source code and a README file explaining 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.)