Please refer to this page for information on how to work on your assignment.
Post's correspondence problem consists of two arrays of words, the first array and the second array. Both arrays have the same length, but the words in it can be of different length. A correspondence is a list of indices which tell how to arrange the elements of the arrays such that both give the same word. Examples can be found in the last lecture, note that the indexing of arrays starts in JavaScript with 0.
(a) Position (0) (1) (2) (3) (4) First Array abb a bab baba aba Second Array bbab aa ab aa a Correspondence 1 1, 0, 0, 3, 0, 4 First word a abb abb baba abb aba Second word aa bbab bbab aa bbab a Correspondence 2 1, 0, 4 First word a abb aba Second word aa bbab a (Thanks to Ryan Flynn for finding this one) (b) Position (0) (1) (2) (3) (4) First Array a aa aba aabb abb Second Array b ba bba bbba bba No correspondence exists
Since this problem is unsolvable, it is impossible to write an algorithm which checks the existence of a correspondence. Nevertheless, one can check whether there is a correspondence of a given length. This should be implemented in this exercise.
The searchcorrespondence()
function has to be implemented. It
obtains three inputs: firstarray
, secondarray
and
indexarray
which are the parameters defining Post's
correspondence problem and the array which will carry the correspondence.
The length of this array is already given. The implementation should cover
two aspects:
indexarray
is (0,0,0,0) and there are five
columns, then the algorithm should check for all entries (a,b,c,d) with
a,b,c,d in {0,1,2,3,4} whether these values of index array define a
solution. The easiest way is to go in lexicographic order through all
these possibilities.
One can use the
printcorrespondence(firstarray, secondarray, indexarray)
function to print the existing solutions and also analyze this function in
order to get an idea of how to test for correspondences. The function to be
edited is the subsearch()
function which is called from
correspondencesearch()
. Here it comes with a parameter
k
which says that indexarray[k]
is now the
variable which has to be set. The subsearch()
function should
call itself with all possible values inserted at
indexarray[k]
. It means that for any possible choice h the
following should be done:
indexarray[k]
should take the value h;firstword + firstarray[h]
instead of
firstword
, secondword + secondarray[h]
instead of secondword
, k + 1
instead of
k
.
Furthermore, please optimize your solution. That is, do not make such a call if it can be eaisly seen that whatever will be done, it will not lead to a match. This optimization will speed up the processing of the search a lot.