5
$\begingroup$

I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://www.algorist.com/algowiki/index.php/Divide-TADM2E#8-22

The problem asks you to write a polynomial-time algorithm using DP which solves a special case of the Word Problem over finite groupoids:

Given a finite groupoid $G$, a word $s$ on $G$ and an $x \in G$, find out whether it is possible to parenthesize $s$, such that its evaluation will yield $x$. Example from the book:

\begin{array}{c|ccc} & a & b & c \\ \hline a & a & c & c \\ b & a & a & b \\ c & c & c & c \\ \end{array}

For instance, consider the above multiplication table and the string $bbbba$. Parenthesizing it $(b(bb))(ba)$ gives $a$, but $((((bb)b)b)a$ gives $c$.

So far I managed to write a naive $O(n!)$ recursive algorithm in Python:

def i(x):
    return ord(x) - ord('a')

def mul(x, y):
    return groupoid[i(x)][i(y)]

# rewrite('abc', 1) = 'ac'
# rewrite('abc', 0) = 'cc'
def rewrite(word, i):
    return word[:i] + mul(word[i], word[i+1]) + word[i+2:]

def search(word, x):
    exists = (word == x)
    for i in range(0, len(word) - 1):
        if exists:
            break
        exists |= search(rewrite(word, i), x)
    return exists

word = sys.argv[1]
x = sys.argv[2]
exists = search(word, x)
print('Solution exists' if exists else 'Unsolvable')

Although we can memoize search, it won't give us polynomial time, since memoization space is of a factorial order. This is where I'm stuck.

The problem here is to somehow reduce the factorial search-space of all possible reductions from $s$ on $G$ to a polynomial search-space, which will depend only on $|s|$ and $|G|$. Can you please help me with that? Any other hints?

$\endgroup$
  • 1
    $\begingroup$ See cs.stackexchange.com/tags/dynamic-programming/info for some guidance on how to approach dynamic programming algorithms. Incidentally, using the same variable name (i) for two purposes is unnecessarily confusing. Also, we'd generally prefer that you avoid sharing specific Python code and instead provide concise pseudocode that doesn't require knowledge of any particular programming language to understand. $\endgroup$ – D.W. Mar 22 at 16:58
  • 1
    $\begingroup$ Hint: study en.wikipedia.org/wiki/Matrix_chain_multiplication $\endgroup$ – D.W. Mar 22 at 16:59
  • $\begingroup$ Matrix chain multiplication is a special case of this problem, where the binary operator satisfies the associative law. $\endgroup$ – Apass.Jack Mar 22 at 21:59
  • 2
    $\begingroup$ Also note the dynamic programming solution for this problem is equivalent to the CYK-algorithm for parsing context-free grammars. The multiplication rules of the groupoid match production rules for a context-free grammar in Chomsky normalform. $\endgroup$ – Hendrik Jan Mar 23 at 13:04
6
$\begingroup$

This word problem over groupoid is a nice example to show the essence of dynamic programming, the recognition of the subproblems. In other words, how can we define the table or the multi-dimensional array that we should fill?

In general, the subproblems should represent the computations that will be repeated many times in a brute-force algorithm. The subproblems should be refined enough so that we can solve the larger subproblems from the solutions of the smaller subproblems. Please take a moment to appreciate how the subproblems are defined below.

Compute $dp[i][j]$, the set of all possible values of $x_{i}x_{i+1}\cdots x_j$, where $1\le i\le j\le n$.

The goal element $a$ is a possible value of $x$ if and only if $dp[0][n]$ contains $a$.

How to compute $dp[i][j]$?

The base case, $dp[i][i]$ is the set of a single element, $x_i$.

How about the case when $j\ge i+1$? Note a parenthesization of $x_ix_{i+1}\cdots x_j$ means to parenthesize it into two parts, $(x_i\cdots x_t)(x_{t+1}\cdots x_j)$ for some $i\le t\lt j$, followed by a parenthesization of the front part $x_i\cdots x_t$ and a parenthesization of the behind part, $x_{t+1}\cdots x_j$. So $dp[i][j]$ contains all products of the form $f\cdot b$, where $f$ is a possible value of the front part and $b$ is a possible of the behind part. Note both the front part and behind part are shorter than the whole, $x_ix_{i+1}\cdots x_j$.

In other word, in order to compute $dp[i][j]$, we can iterate $f$ through all elements in $dp[i][t]$ and $b$ through all elements in $dp[t+1][j]$, adding the product $f\cdot b$ to $dp[i][j]$.

There are $n(n-1)/2$ choices for $i$ and $j$. There are at most $n$ choices for $t$. There are at most $k$ choices for $f$. There are at most $k$ choices for $b$. Depending on the implementation, it takes $O(k\cdot k\cdot k)$ or much less time to compute product $f\cdot b$ and add it to a set of at most $k$ elements. Hence the time-complexity of the algorithm is polynomial in $n$ and $k$.

$\endgroup$
  • $\begingroup$ @j_random_hacker As you observed, that statement in my previous answer is somewhat ambiguous. Please check my revamped answer. $\endgroup$ – Apass.Jack Mar 25 at 13:55
  • $\begingroup$ Thanks, what you have now is even clearer than what I asked for :) I'll delete my original comment. $\endgroup$ – j_random_hacker Mar 25 at 14:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.