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.

  • 0
    @FarhadYusufali: "Dynamic programming" is not an algorithm, it is a vague idea that can be used for developing algorithms in general. Are you claiming claim that there is exactly one possible way to apply this general idea to the specific problem of matrix multiplication? If you understand the idea and the problem well enough to be sure of that, why do you need to as$k$ anyth$i$ng about it?2012-08-28

1 Answers 1

1

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.

  • 0
    @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 '('.2012-10-28