CODEWITHSUNDEEP
algorithmdynamic-programming
venkysmarty
venkysmarty

Reputation: 11431

subproblem graph for matrix multiplication using dynamic programming

I am reading about dynamic programming in cormen.

Related back ground can be found at following link

http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap16.htm

Usually, the subproblem graph gives an alternative way to perform the runtime analysis of dynamic programming. Each vertex corresponds to a subproblem, and the choices for a subproblem are the edges incident from that subproblem. Recall that in rod cutting,the subproblem graph had n vertices and at most n edges per vertex, yielding an O(n^2) running time. For matrix-chain multiplication, if we were to draw the subproblem graph, it would have O(n^2) vertices and each vertex would have degree at most n - 1, giving a total of O(n^3) vertices and edges.

I am looking for matrix-chain multiplication subproblem graph for simple example n = 4.

Thanks for your time and help

Upvotes: 2

Views: 3526

Answers (1)

Juan Lopes
Juan Lopes

Reputation: 10565

I'm not sure if I understand your question, but are you looking for something like this?

subproblem graph

I created it using this simple Python script:

n = 4
print 'digraph {'
for i in range(n):
    for j in range(i, n):
        print 'p{}{} [label="M[{},{}]"];'.format(i,j,i+1,j+1)

for i in range(n):
    for j in range(n):
        for k in range(i, j):
            print 'p{}{} -> p{}{}'.format(i,j,i,k)
            print 'p{}{} -> p{}{}'.format(i,j,k+1,j)
print '}'

Run like this (needs graphviz and imagemagick installed):

python test.py | dot -Tpng | display

Upvotes: 5

Related Questions