6
$\begingroup$

The following are questions about using dynamic programming for matrix chain multiplication. Pseudocode can be found in the Wikipedia article on matrix chain multiplication.

1) Why is the time complexity for trying all bracket permutations $\mathcal{O}(2^n)$, where $n$ is the number of matrices??

2) Why are there $\frac{n^2}{2}$ unique subsequences? (This question is refering to memoization where all unique subproblems are stored. A rephrasing of this question would be: Why are there $\frac{n^2}{2}$ unique subproblems to be stored?)

3) Why does using memoization reduce the time to $O(n^3)$?

I don't have made any progress on the above questions, therefore there is no work for me to show.

$\endgroup$
9
  • $\begingroup$ Why the down vote? This is a legitimate question - it hasn't been answered before, it explains the lack of self work and is on-topic. $\endgroup$
    – user26649
    Commented Aug 27, 2012 at 22:22
  • $\begingroup$ I did not downvote, but I presume it got downvoted because it seems you haven't given it much thought. E.g. for question 4) - you can't multiply matrices that don't share a dimension AT ALL - so an algorithm to compute the most efficient multiplication routine cannot work if the matrix dimensions don't match up. $\endgroup$
    – us2012
    Commented Aug 27, 2012 at 22:35
  • 2
    $\begingroup$ @us2012 That was stupid of me. Sorry, I haven't worked with linear algebra for a while, resulting in me asking stupid questions like the one above. I removed it. Thanks for politely pointing it out! $\endgroup$
    – user26649
    Commented Aug 27, 2012 at 22:38
  • 1
    $\begingroup$ It's on-topic IMO (+1) $\endgroup$
    – Belgi
    Commented Aug 27, 2012 at 22:49
  • $\begingroup$ Asking a question about a particular construction that "can be found" somewhere in a Wikipedia article which you don't even bother to link to (and which may be completely rewritten by the time a future reader attempts to make sense of your question), is close to earning this a downvote from me. $\endgroup$
    – hmakholm left over Monica
    Commented Aug 27, 2012 at 23:20

1 Answer 1

Reset to default
1
$\begingroup$

The combinatorial background related to bracket permutations (plus loads of other things) can be found on the wikipedia page on Catalan numbers: http://en.wikipedia.org/wiki/Catalan_number . This may be overkill for your applications, I'm sure there is a nice and quick way to give your desired $\mathcal{O}(2^n)$ bound along the lines that Belgi was considering in his answer. I will update this if I can think of anything.

The number of subsequences can be estimated as such: There are $n-1$ subsequences starting with the first matrix (1 of length 2, ..., 1 of length $n$), $n-2$ subsequences starting with the second matrix, etc, which gives a total of $(n-1)+(n-2)+...+1=\frac{n(n-1)}{2} = \mathcal{O}(n^2)$ such subsequences.

$\endgroup$
4
  • $\begingroup$ Thanks! Any chance you know an answer to question 3? $\endgroup$
    – user26649
    Commented Aug 27, 2012 at 23:24
  • $\begingroup$ I thought about Catalan numbers, but from a sequence of just bracket I can't generate the multiplication with the bracket and the $A_i$'s. I can now code multiplication with the bracket (included nested ones) into a binary string, but I can't evaluate it's size because I am having problems determning the number of $'('$ a string with bracket and the $A_i$'s can have). $\endgroup$
    – Belgi
    Commented Aug 27, 2012 at 23:35
  • $\begingroup$ The coding is replacing $($ and $)$ with 1 and $A_i$ with $0$. this map is $1-1$ but it remains to determine how many $($ are allowed...we need to be carefull not to include something like $(((A_1)))A_2$. this is legal writing but there are pairs of bracket we can remove... $\endgroup$
    – Belgi
    Commented Aug 27, 2012 at 23:37
  • $\begingroup$ @Belgi Reduction to catalan numbers (the bracketing model): write the multiplication in postfix (i.e. reverse polish). Then replace each matrix with '(' and each $\cdot$ with ')'. Remove the first '('. $\endgroup$
    – ronno
    Commented Oct 28, 2012 at 9:15

You must log in to answer this question.