## Programming Assignment 1

Assigned: Jan. 18.
Due: Feb. 8.

#### Assignment

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 forward.) 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.

#### Input

Your code should accept the following inputs:
• 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 both stages.
• D. A flag indicating the type of output, as described below.
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:
• 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.
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.