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
    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.2012-08-27
  • 0
    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.2012-08-27
  • 2
    @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!2012-08-27
  • 1
    It's on-topic IMO (+1)2012-08-27
  • 0
    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.2012-08-27
  • 0
    @HenningMakholm I disagree. This question is completely independent of the Wikipedia page. The question can be answered without any reference to Wikipedia. The only reason I mentioned Wikipedia is simply to help those without familiarity of the algorithm. The questions assumes that people who are attempting to answer already know the algorithm.2012-08-27
  • 0
    @FarhadYusufali: Your only specification about _which_ algorithm your question is about is by reference to the Wikipedia article (implicitly, I assume, your specification is "whichever algorithm the Wikipedia article presented at the time I wrote this").2012-08-27
  • 0
    @HenningMakholm That *isn't* my only specification. My question specifically states: "The following are questions about using dynamic programming for matrix chain multiplication. ". This informs the reader exactly *which* algorithm I am talking about.2012-08-27
  • 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 ask anything 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
    Thanks! Any chance you know an answer to question 3?2012-08-27
  • 0
    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).2012-08-27
  • 0
    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...2012-08-27
  • 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