Need help on Matrix chain order problem

B

Bob

All,

I am new to this group. I just started learning Java. I have an
algorithm to impement in Java. I am having problems using Java. Can any
one help me to code this in Java.
Problem: Find an optimal parenthesization of a matrix-chain product
whose sequence of dimensions is 〈30, 35, 15, 5 , 10, 20, 25〉

MATRIX-CHAIN-ORDER(p)
1 n ↠length[p] - 1
2 for i ↠1 to n
3 do m[i, i] ↠0
4 for l ↠2 to n ▹l is the chain length.
5 do for i ↠1 to n - l + 1
6 do j ↠i + l - 1
7 m[i, j] ↠∞
8 for k ↠i to j - 1
9 do q ↠m[i, k] + m[k + 1, j] + pi-1 pkpj
10 if q < m[i, j]
11 then m[i, j] ↠q
12 s[i, j] ↠k
13 return m and s

________________________________________________________________

PRINT-OPTIMAL-PARENS(s, i, j)
1 if i = j
2 then print "A"i
3 else print "("
4 PRINT-OPTIMAL-PARENS(s, i, s[i, j])
5 PRINT-OPTIMAL-PARENS(s, s[i, j] + 1, j)
6 print ")"

For ex: it should print in the form of ((A1 (A2 A3)) ((A4 A5)A6)).

Thanks,
Bob.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,768
Messages
2,569,574
Members
45,050
Latest member
AngelS122

Latest Threads

Top